这里想不明白
来源：9-5 0-1背包问题
IT_god
2020-10-22
有一个容量为5的背包。
从递归解决的角度， n = 3, C = 5 . 那么结果就是我现在要求的F（2， 5）。 也就是我在上图中标记了“？”的值
"step"为子问题
根据状态转移方程 ？ = max(step1.1, v(2) + step1.2).
step1.1 = max(step2.1, v(1)+step2.2);
step1.2 = max(step2.3, v(1)+step2.4) ;
那么我的问题来了， I : 这一轮递归下来， 求‘？’设计的那么些子问题（step）， 并没有发生重叠呀， 该怎么理解递归解决背包问题的重叠子问题的“重叠”呢?
II: 这里求最终解”？“看似并没有涉及所有的状态（index, c)呀, 上图中只涉及了step出现的地方。 那岂不是不需要视频里讲动态规划解决背包问题哪有一个个格子填满的功夫了吗？
以上就是我的两个想不明白问题， 希望得到老师的帮助！
1回答
-
1）
这个测试用例太小了，看不出重叠。我可以给你提供一个稍微大一点儿的测试用例：
6 15 // 6 个物品，填充容量为 15 的背包，下面 6 行是每个物品对应的体积和价值
6 5
5 6
6 4
6 6
3 5
7 2
你可以这样修改记忆化搜索过程：
int bestValue(const vector<int> &w, const vector<int> &v, int index, int c){ if(c <= 0 || index < 0) return 0; // 不做记忆化搜索 // if(memo[index][c] != -1) // return memo[index][c]; // 打印出这次计算的状态 index, c cout << index << " " << c << endl; int res = bestValue(w, v, index-1, c); if(c >= w[index]) res = max(res, v[index] + bestValue(w, v, index - 1, c - w[index])); memo[index][c] = res; return res; }你应该可以看到打印出多组相同的 index 和 c 的数据对，每一组都是一次重复搜索。
当然，这个测试用例也不大，但是足以演示重复搜索是存在的。你要有兴趣，可以再跟踪一下重复搜索是如何出现的。
2
是的。记忆化搜索有可能不需要把所有的状态都计算出来，就能算出最终需要的结果。所以有的时候，记忆化搜索比动态规划快。要看状态的定义。但有的时候，肯定要计算出所有状态，比如斐波那契数列。
继续加油！：）
012020-10-23
相似问题