java - 如何知道在背包问题(DP实现)中选择了哪个项目？

Question

我正在根据这段代码实现背包问题，我想知道最终选择了哪些元素。

代码:

Knapsack { 


static int max(int a, int b)  { return (a > b) ? a : b; } 


static int knapSack(int W, int wt[], int val[], int n) 
{ 
    int i, w; 
    int K[][] = new int[n + 1][W + 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) 
                K[i][w] = 0; 
            else if (wt[i - 1]<= w) 
                K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]); 
            else
                K[i][w] = K[i - 1][w]; 
        } 
    } 

    return K[n][W]; 
} 


public static void main(String args[]) 
{ 
    int val[] = new int[] { 60, 100, 120 }; 
    int wt[] = new int[] { 10, 20, 30 }; 
    int W = 50; 
    int n = val.length; 
    System.out.println(knapSack(W, wt, val, n)); 

     } 

  } 

不过，我想做的是根据元素最初存储在数组中的方式，找到最终插入背包的元素，并将这些结果以二进制格式存储在文件中。

我的意思是，这段代码中有 3 个项目，如果例如项目编号 1(值为 60 的项目)和项目编号 3(值为 120 的项目)是终于选择了，我想要一个看起来像 1,0,1 的字符串

Answer 1

您可以在返回语句之前的代码中添加以下内容:

        int ind = n;
        int weight = W;
        String s = "";
        while (ind > 0) {
            if (K[ind][weight] != K[ind - 1][weight]) {
                s = "1," + s;
                weight -= wt[ind - 1];
            }
            else {
                s = "0," + s;
            }
            ind -= 1;
        }
        s = s.substring(0, s.length() - 1);
        System.out.println(s);

此代码实质上是从最终解决方案回溯，以查看 i 项的最大值是否等于 i - 1 项的最大值(这表明是否使用了第 i 项)。

将此添加到您的代码后，我得到以下输出，看起来是正确的:

0,1,1
220