所以我正在查看来自 this website 的这段代码关于背包0-1问题。
我想修改他们提供的程序,以便它返回选择了哪些值以及相应的索引。例如,对于这种情况,解决方案输出 390,但我希望它也打印出已选择的值。所以在这种情况下,我希望它打印:
Items selected :
#2 60
#3 90
#5 240
这是我目前所拥有的:
// A Dynamic Programming based solution for 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(int W, int wt[], int val[], int n)
{
int i, w;
int K[][] = new int[n+1][W+1];
int[] selected = new int[n + 1];
// Build table K[][] in bottom up manner
for (i = 0; i <= n; i++)
{
for (w = 0; w <= W; w++)
{
if (i==0 || w==0){
//selected[i] = 1;
K[i][w] = 0;
}
else if (wt[i-1] <= w){
selected[i] = 1;
K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]);
}
else{
selected[i]=0;
K[i][w] = K[i-1][w];
}
}
}
System.out.println("\nItems selected : ");
for (int x = 1; x < n + 1; x++)
if (selected[x] == 1)
System.out.print(x +" ");
System.out.println();
return K[n][W];
}
// Driver program to test above function
public static void main(String args[])
{
int val[] = new int[]{300,60,90,100,240};
int wt[] = new int[]{50,10,20,40,30};
int W = 60;
int n = val.length;
System.out.println(knapSack(W, wt, val, n));
}
}
我所做的是创建一个 int 类型的一维数组,以在选择该值时将索引标记为 true。或者至少,这就是我想要做的。
但是这是打印每个索引。在我弄清楚那部分之前,我不知道如何返回相应的权重。我知道我在代码中的逻辑是错误的,所以有人可以指出我正确的方向吗?
最佳答案
不幸的是,在处理动态规划问题时很难设置选择哪些项目。由于解决方案必然建立在子问题的解决方案之上,因此您还需要存储在每个子解决方案中选择的项目,然后在最后汇总这些项目。
幸运的是,有更好的方法。我们可以使用最终解决方案回溯并查看我们最终使用的值。只需将打印值的部分替换为:
System.out.println("\nItems selected : ");
int tempW = W;
int y = 0; //to index in selected
for (int x = n; x > 0; x--){
if ((tempW-wt[x-1] >= 0) && (K[x][tempW] - K[x-1][tempW-wt[x-1]] == val[x-1]) ){
selected[y++] = x-1; //store current index and increment y
tempW-=wt[x-1];
}
}
for(int j = y-1; j >= 0; j--){
System.out.print("#" + (selected[j]+1) + " ");
System.out.println(val[selected[j]]);
}
这将打印:
Items selected:
#2 60
#3 90
#5 240
390
要按升序打印项目,我们必须在单独的 for
循环中存储和打印它们。这与我们首先必须回溯的原因相同:从起点有很多路可走,而从终点只有一条路可以回到起点。
关于java - 这个Knapsack java代码中如何返回重量和对应的索引?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/45405662/