浅语清风2020-09-25课程难度越来越大了，对于对于初学者来说看一遍是根本不够的，要反复学习，不断积累，编程实践。我一定要攻克动态规划的难关！作者回复: 我们一起加油！有任何相关问题，都欢迎留言讨论。我也会尽我所能帮你解答。
9
BBQ2021-03-10感谢老师的细心讲解，怎么感觉越写越简单了呢。 😀 把空间复杂度优化了一下，用一个一维数组，倒着走，就不会产生重复计算了。 def lastStoneWeightII(self, stones: List[int]) -> int: total = sum(stones) size = (total)//2+1 #这个要注意，如果容量要达到size，大小要是size + 1 dp = [0] * size for i in range(len(stones)): j = size - 1 while j >= stones[i]: dp[j] = max(dp[j], dp[j-stones[i]] + stones[i]) j-= 1 return total - dp[-1] - dp[-1]作者回复: 恩，这样处理没有问题。顶上去，让大家看到。
3
冬风向左吹2020-11-07没太理解这里：dp[tn-1][rw-w[tn]] + v[tn]。放入物品前的价值+放入特别的价值。为什么放入特别前的价值 rw-w[tn]，这里要减w[tn]呢。放入物品前的价值不就是dp[tn-1][rw]吗？作者回复: 并不是这样，因为 dp[tn][rw]是背包在处理第tn个物品后背包剩余rw容量的最优解，那么如果我们没有把第tn件物品放进去，那么肯定就是dp[tn-1][rw]。当时如果我们要把第tn件物品放进去，那么放进去背包之后容量就只剩下了rw-w[tn]，所以需要取得就是dp[tn-1][rw-w[tn]]（也就是在容量只剩下rw-w[tn]得情况下，处理第tn-1个物品时最优是多少）。
共 4 条评论2
Roy Liang2020-10-19#include <iostream> #include <vector> #include <cmath> #include <cstring> using namespace std; int DP(const std::vector<int>& w, const std::vector<int>& v, int N, int W) { int dp[N+1][W+1]; memset(dp, 0, sizeof(dp)); // 创建备忘录 for (int tn = 1; tn < N + 1; tn++) { // 遍历每一件物品 for (int rw = 1; rw < W + 1; rw++) { // 背包容量有多大就还要计算多少次 if (rw < w[tn]) { // 当背包容量小于第tn件物品重量时，只能放入前tn-1件 dp[tn][rw] = dp[tn-1][rw]; } else { // 当背包容量还大于第tn件物品重量时，进一步作出决策 dp[tn][rw] = max(dp[tn-1][rw], dp[tn-1][rw-w[tn]] + v[tn]); } } } return dp[N][W]; } int main() { int N, i, sum = 0, t, part1, part2; vector<int> w, v; w.push_back(0); v.push_back(0); cin >> N; for (i = 1; i <= N; i++) { cin >> t; sum += t; w.push_back(t); v.push_back(t); } part1 = DP(w, v, N, sum / 2); part2 = sum - part1; cout << abs(part1 - part2) << endl; }展开作者回复: 赞，没问题。顶上去！
2
coder2021-12-21关于粉碎石头（力扣上的题：1049. 最后一块石头的重量 II）的问题的思考： 1. 可以把石头分为两堆，这两堆的重量尽量均衡，才能产生最小的差值 2. 那么就相当于把所有石头的总重量除以2，作为背包的容量，然后看最大能装入多少重量的石头 3. 从而转化成背包问题作者回复: 这样是可以的。赞，让大家看到。
共 2 条评论1
樟树林2021-01-20老师，关于背包问题哈，背包容量为2，物品个数为3的背包，按照你上述计算得出的结果是3，但实际结果应为6。这个问题，老师能解释一下吗？作者回复: 这个背包内可以容纳的物品只取决于背包的容量和物品的重量，示例数据里背包容量为2的情况下，最优解肯定是3，因为永远只能装下一个物品，这个是不是对问题的理解有什么偏差。
共 4 条评论1
风清扬2023-03-05 来自广东参考评论里 Roy Liang的代码，修改了下代码，添加了部分注释： #include <iostream> #include <vector> #include <cmath> #include <cstring> #include <numeric> // std::accumulate using namespace std; int DP(const std::vector<int>& w, const std::vector<int>& v, int N, int W) { //DP[i][j]，当可以选择前i(含)个物品时，背包容量为j时最大的价值 int dp[N+1][W+1]; memset(dp, 0, sizeof(dp)); // 创建备忘录 for (int tn = 1; tn < N + 1; tn++) { // 遍历每一件物品 for (int rw = 1; rw < W + 1; rw++) { // 背包容量有多大就还要计算多少次 if (rw < w[tn]) { // 当背包容量小于第tn件物品重量时，只能放入前tn-1件 dp[tn][rw] = dp[tn-1][rw]; } else { // 当背包容量还大于第tn件物品重量时，进一步作出决策 dp[tn][rw] = max(dp[tn-1][rw], dp[tn-1][rw-w[tn]] + v[tn]); } } } return dp[N][W]; } int main() { int N = 6; //粉碎石头问题转换为0-1背包，这里价值与重量相同 vector<int> w = {0,1,2,1,7,9,4}; vector<int> v = {0,1,2,1,7,9,4}; //计算当前所有石头的重量和 int sum = std::accumulate(w.begin(),w.end(),0); //转换为0-1背包问题，在背包容量为sum/2的情况下，尽量让价值最大（重量最大）接近sum/2,因此part2-part1绝对值越小 int part1 = DP(w, v, N, sum / 2); int part2 = sum - part1; cout << "part1:"<<part1<<",part2:"<<part2<<",abs:"<<abs(part1 - part2) << endl; return 0; }展开作者回复: 给你点个赞，注释能帮助到更多人！
小灰2022-04-07根据老师的代码，我用了 C#实现，请老师赐教，代码如下: /// <summary> /// 0-1 背包问题（针对当前物品，是放入背包，还是不放入背包时的价值最大） /// </summary> /// <returns></returns> public int KnapsackDP(int[] wtItems, int[] valItems, int total, int maxWeight) { // 创建备忘录 int[,] dpItems = new int[total + 1, maxWeight + 1]; // 初始化状态 //for (int i = 0; i < N + 1; i++) { dpItems[i,0] = 0; } //for (int j = 0; j < W + 1; j++) { dpItems[0,j] = 0; } for (int tn = 1; tn < total + 1; tn++) // 遍历每一件物品 { for (int rw = 1; rw < maxWeight + 1; rw++) // 背包容量有多大就还要计算多少次 { if (rw < wtItems[tn]) // 当背包容量小于第 tn 件物品重量时，只能放入前tn-1件 { dpItems[tn, rw] = dpItems[tn - 1, rw]; } else { // 当背包容量还大于第tn件物品重量时，进一步作出决策 dpItems[tn, rw] = Math.Max(dpItems[tn - 1, rw], dpItems[tn - 1, rw - wtItems[tn]] + valItems[tn]); } } } return dpItems[total, maxWeight]; } [TestCaseSource("KnapsackSource")] public void KnapsackDPTest(int[] wtItems, int[] valItems, int total, int maxWeight, int expectedMaxVal) { var maxVal = KnapsackDP(wtItems, valItems, total, maxWeight); // 输出答案 Console.WriteLine($"KnapsackDPTest,maxVal:{maxVal},expectedMaxVal:{expectedMaxVal}"); Assert.AreEqual(expectedMaxVal, maxVal); } public static IEnumerable KnapsackSource() { yield return new TestCaseData(new int[] { 0, 3, 2, 1 }, new int[] { 0, 5, 2, 3 }, 3, 5, 8); }展开作者回复: 这段C#代码没有问题。赞。
- alex_lai2022-01-27dp[n,w]中的n 不是表示第几个item在还剩w空间的情况下的最优解 而是总共可以选n个item在w空间里的最优解吧？！ 我的意思n的值跟顺序无关，比如dp[1, 10] 就是选一个item给10的空间 最优是多少
作者回复: 这里n的确指的是处理第n个物品后的最优解，的确不是选了几个item。只不过你调整物品的顺序肯定也不影响这个最优解而已。
- coder2021-12-21背包基本问题，做决策部分：“如果背包容量小于当前物品价值” 应该是“小于当前物品重量”或者“小于当前物品体积”吧？
作者回复: 是的，应该是背包容量小于当前物品重量或者体积