打印从Knapsack Unbounded算法中选择的项目？

Question

我知道标准的knapsack是如何工作的，我有能力打印2D矩阵中选择的项目，但是据我所知，无界knapsack是一个1D阵列。如何打印无界knapsack算法选择的项目？

Answer 1

Unbounded Knapsack可以使用2D矩阵来解决，这样就可以轻松打印所包含的物品。可以从矩阵中回溯knapsack中包含的项目，方法和01 Knapsack一样。

在填充了dp[][]矩阵后，就可以打印出包含的项目。

// dp[val.length+1][sackWeight+1] is the matrix for caching.
// val[] is the array that stores the values of the objects
// and wt[] is the array that stores the weight of the corresponding objects.
int x = val.length, y = sackWeight;
    while (x > 0 && y > 0) {
        if (dp[x][y] == dp[x - 1][y])
            x--;
        else if (dp[x - 1][y] >= dp[x][y - wt[x - 1]] + val[x - 1]) 
            x--;
        else {
            System.out.println("including wt " + wt[x - 1] + " with value " + val[x - 1]);
            y -= wt[x - 1];
        }
    }