如何在此Knapsack java代码中返回权重和相应的索引？

Question

所以我在这里从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类型的1-d阵列标记索引如果选择了该值，则为true。或者至少，这就是我想要做的。

但是这是打印每个索引。直到我弄清楚这一部分之前，我不知道如何返回相应的权重。我知道我在代码中的逻辑是错误的，所以有人可以指引我正确的方向？

Answer 1

不幸的是，当您在动态编程问题中进行选择时，很难设置哪些项目被选中。由于解决方案必须建立子问题的解决方案，因此您需要将选定的项目存储在每个子解决方案中，然后在最后对其进行汇总。

幸运的是，还有更好的方法。我们可以使用最终解决方案回溯，看看我们最终使用的是什么值。只需更换其中可以使用打印您的值的段落：

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循环打印出来。这也是出于同样的原因，我们必须首先回溯：从起点开始，有很多路要走，而从终点来看，只有一条路返回起点。