algorithm - 从背包中取回元素【一维数组实现】

Question

这个算法工作正常Are these 2 knapsack algorithms the same? (Do they always output the same thing)

我们如何检索在此过程中选择的项目？

这是上一篇文章的算法

for (int j = 0; j < N; j++) {
    if (C-w[j] < 0) continue;
    for (int i = C-w[j]; i >= 0; --i) { //loop backwards to prevent double counting
        dp[i + w[j]] = max(dp[i + w[j]], dp[i] + v[j]); //looping fwd is for the unbounded problem
    }
}
printf( "max value without double counting (loop backwards) %d\n", dp[C]);

这是一个例子:

For C = 9 and N = 3

Values and Weights: 
5 4
6 5
3 2

背包数组如下:

0 0 3 3 5 6 8 9 9 11 

通过选择项目 1 和项目 2 给出最优值 = 11

如何检索选中的项目？或者如何知道我们选择了哪些项目？[第 1 项和第 2 项]

添加另一个示例:

weight: 16 19 23 28
value: 2 3 4 5
C = 7

迭代 1

0 16 16 16 16 16 16

迭代 2

0 16 19 19 35 35 35

迭代 3

0 16 19 23 35 39 42

迭代 4

0 16 19 28 35 39 44

项目 1 和 4 的最优值 = 44

Answer 1

通过检查刚刚找到的解决方案是否比以前看到的任何解决方案更好来简单地替换您的最大调用。如果是这样，请将其存放起来以备后用。