我有一个背包问题的简单解决方案的代码，我想获取所选项目的索引列表，目前它正在返回所选项目的总值。 任何帮助将不胜感激。 Java 代码:
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
/* A Naive recursive implementation of 0-1 Knapsack problem */
class Knapsack
{
// A utility function that returns maximum of two integers
static int max(int a, int b) {
return (a > b)? a : b; }
// Returns the maximum value that can be put in a knapsack of capacity W
static int knapSack(float W, float wt[], int val[], int n)
{
// Base Case
if (n == 0 || W == 0)
return 0;
// If weight of the nth item is more than Knapsack capacity W, then
// this item cannot be included in the optimal solution
if (wt[n-1] > W)
{
return knapSack(W, wt, val, n-1);
}
// Return the maximum of two cases:
// (1) nth item included
// (2) not included
else {
return max( val[n-1] + knapSack(W-wt[n-1], wt, val, n-1),
knapSack(W, wt, val, n-1)
);
}
}
// Driver program to test above function
public static void main(String args[])
{
int val[] = new int[]{29,74,16,55,52,75,74,35,78};
float wt[] = new float[]{85.31f,14.55f,3.98f,26.24f,63.69f,76.25f,60.02f,93.18f,89.95f};
float W = 75f;
int n = val.length;
System.out.println(knapSack(W, wt, val, n));
}
}
当前结果:148 预期结果:2,7
最佳答案
这里是你如何做到的(尽管它使用了一些额外的内存)-
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
/* A Naive recursive implementation of 0-1 Knapsack problem */
class Knapsack
{
// A utility function that returns maximum of two integers
static int max(int a, int b) {
return (a > b)? a : b; }
// Returns the maximum value that can be put in a knapsack of capacity W
static int knapSack(float W, float wt[], int val[], int n,int visited[])
{
// Base Case
if (n == 0 || W == 0)
return 0;
// If weight of the nth item is more than Knapsack capacity W, then
// this item cannot be included in the optimal solution
if (wt[n-1] > W)
{
return knapSack(W, wt, val, n-1,visited);
}
// Return the maximum of two cases:
// (1) nth item included
// (2) not included
else {
int v1[]=new int[visited.length];
System.arraycopy(visited, 0, v1, 0, v1.length);
int v2[]=new int[visited.length];
System.arraycopy(visited, 0, v2, 0, v2.length);
v1[n-1]=1;
int ans1 = val[n-1] + knapSack(W-wt[n-1], wt, val, n-1,v1);
int ans2 = knapSack(W, wt, val, n-1,v2);
if(ans1>ans2){
System.arraycopy(v1, 0, visited, 0, v1.length);
return ans1;
}
else{
System.arraycopy(v2, 0, visited, 0, v2.length);
return ans2;
}
}
}
// Driver program to test above function
public static void main(String args[])
{
int val[] = new int[]{29,74,16,55,52,75,74,35,78};
float wt[] = new float[]{85.31f,14.55f,3.98f,26.24f,63.69f,76.25f,60.02f,93.18f,89.95f};
float W = 75f;
int n = val.length;
int visited[] = new int[n];
System.out.println(knapSack(W, wt, val, n, visited));
for(int i=0;i<n;i++)
if(visited[i]==1)
System.out.println(i+1);
}
}
我所做的是我创建了一个已访问数组，如果使用了当前元素而不是我将当前元素标记为已访问，则它保持为零。最后，我遍历了这个数组并打印了每个访问过的元素为 1
关于java - 如何获取0-1背包中选中的元素列表？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/45995949/