关于bestValue()方法的描述

Question

// 用 [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中所有元素都计算后才能得出结果。
感觉有点自相矛盾，老师能再帮我解释下吗？ 谢谢

Answer 1

liuyubobobo 2020-04-28 02:52:44

不对。这个函数的语义是：用 [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 的地方。

• 提问者 慕妹2978617 #1

  谢谢老师的耐心回答，8，9，10都是我一点未接触过的内容，所以比较吃力。基础数据结构算法也是看的老师的另外两个课程,所以这三节对我的难度还是不小。还好有老师耐心帮助

• liuyubobobo 回复 提问者 慕妹2978617 #2

  继续加油！：）

Answer 2

提问者 慕妹2978617 2020-04-27 22:47:02

还有就是为什么我们要从后向前呢？直接从前向后有什么弊端吗？

• liuyubobobo #1

  我没有理解你说的“直接从前向后”是什么意思？把你的想法用代码表示出来？

• 提问者 慕妹2978617 回复 liuyubobobo #2

  传入得参数是len-1，w的最后一个元素，然后不断判断index-1，每次参数规模缩小1。但是根据我们平时的思路都是起始传入0，而不是len-1 然后让 index+1，从0开始向len方向看，我觉得这样是从前往后。这个从len-1开始，总是感觉理解起来有些绕，有点别扭，理解不好

• liuyubobobo 回复 提问者 慕妹2978617 #3

  因为我们的状态定义是 从 [0...index] 的物品,填充容积为c的背包的最大价值，所以最终结果就是要求状态 bestValue(len - 1, C)。

点开查看后面1条评论