关于bestValue()方法的描述
来源：9-5 0-1背包问题
慕妹2978617
2020-04-27
// 用 [0...index]的物品,填充容积为c的背包的最大价值
private int bestValue(int[] w, int[] v, int index, int c){
if(c <= 0 || index < 0)
return 0;
if(memo[index][c] != -1)
return memo[index][c];
int res = bestValue(w, v, index-1, c);
if(c >= w[index])
res = Math.max(res, v[index] + bestValue(w, v, index - 1, c - w[index]));
return memo[index][c] = res;
}
老师您好，关于背包问题 这个方法的描述是不是不准确呢？
首先index是从n-1开始的 也就是说是从w中的最后一个元素开始往前遍历依次添加进res中，
根据终止条件:
如果c<=0 那么这个范围是[index…len-1]
如果index<0 那么这个范围是[0…len-1]
综上这个方法的作用应该是：
用 [index…len-1]的物品,填充容积为c的背包的最大价值
因为index不一定100%遍历到0
但是根据思想我们一定要遍历到inde=0为止 ，因为我们要把w中所有元素都计算后才能得出结果。
感觉有点自相矛盾，老师能再帮我解释下吗？ 谢谢
写回答
2回答
-
不对。这个函数的语义是：用 [0...index] 的物品,填充容积为c的背包的最大价值。
为了找到从 [0...index] 的物品,填充容积为c的背包的最大价值，
我们对于第 index 个物品，我们或者不选择它：也就是 bestValue(w, v, index-1, c);
或者选择它，也就是 v[index] + bestValue(w, v, index - 1, c - w[index])
注意，我们的递归调用参数是 index -1，
也就是在 从 [0...index - 1] 的物品填充背包结论的基础上，计算[0...index] 的物品,填充容积为c的背包的最大价值。
因为每次都是 index - 1，最终递归调用一定能到 index == 0 的地方。
022020-04-28 -
慕妹2978617
提问者
2020-04-27
还有就是为什么我们要从后向前呢？直接从前向后有什么弊端吗？
042020-04-28
相似问题