chapter_dynamic_programming/knapsack_problem/

[giscus[bot]]

chapter_dynamic_programming/knapsack_problem/

动画图解、一键运行的数据结构与算法教程

https://www.hello-algo.com/chapter_dynamic_programming/knapsack_problem/

[bethewind]

感觉方法1和方法2是根据状态转移方程硬写的,只是动态规划的递归写法.最小路径的方法1和方法2也是这样的,
觉得第1个例子爬楼梯从暴力/记忆化搜索推到动态规划就可以了,后面例子直接写动态规划的实现就好了.
感觉回溯法还是数据结构与算法之美里的写法更合适些:从0往后推

// 回溯算法实现
private int maxV = Integer.MIN_VALUE; // 结果放到 maxV 中
private int[] weight = {2 , 2 , 4 , 5}; // 物品重量
private int[] value = {3 , 4 , 8 , 9 , 6}; // 物品的价值
private int n = 4; // 物品个数
private int w = 8; // 背包容量
//f(i,cw,cv) 表示将要决策第 i 个物品是否装入背包
//cw,cv 表示决策前当前背包中物品的总重量和总价值
    public void f(int i, int cw, int cv) { // 调用 f(0, 0,0)
        if (cw == w || i == n) { // cw==w 表示装满了, i==n 表示物品都考察完了
            if (cv > maxV)
                maxV = cv;
            return;
        }
        for (int x = 0; x < 2; x++) {  //0,1不放i和放i两种选择
            cw += x * weight[i];//做选择
            cv += x * value[i];
            if (cw <= w)
                f(i + 1, cw, cv);
            cw -= x * weight[i];//回退选择
            cv -= x * value[i];
        }
    }

[krahets]

是的。回溯是基于“选择”构建的，因此应该是正向，从第 1 个物品开始选。对应地，暴力搜索是基于“子问题分解”角度构建的，因此是逆向，在递归中不断走向更小的子问题。

[feiaiyue]

如何返回背包里所放置的物品呢？以及0-1背包问题是否有多个解（里面包含不同的物品）

[krahets]

若想要返回放置物品的方案，则需要记录放置结果。这个也可以先用暴力搜索实现（和回溯记录状态一样），然后再将它记忆化，改为递推。

是可能具有多个解的。举个例子，假设两个物体 w1 = 2 * w2 , v1 = 2 * v2 ，那么 v1 可以被两个 v2 等价替换。

[Li-99]

能否考虑”from functools import cache“实现记忆化搜索，我感觉这样记忆化搜索理解起来更简单

[krahets]

可以呀，Python 的 cache 可以显著简化记忆化递归的代码实现～

[rangeryx-66]

老师您好，我想请教一下，假如背包还有一个类似重量的元素，但是要求这个元素的总和必须大于某个值该怎么处理

[krahets]

您好，没太看懂这个问题

[rangeryx-66]

题目是这样的：
小军前来买瓜。
众所周知，水果摊里的西瓜的瓜皮子和瓜粒子都是金粒子做的。小军当然想获得尽可能多的金粒子。
一共有 n 个瓜，每个瓜有重量 w ，成熟度 v ，金粒子数量 g 。
虽然小军的钱是无限的，但他的电动车载重是有限的，因此他不能买总重量超过 W 的瓜。当小军买的瓜的总成熟度小于 V 时， 瓜摊并不会把瓜卖给他。
具体的：水果摊一共有 n 个瓜，每个瓜有重量 w ，成熟度 v ，金粒子数量 g 。一共有 q 次询问，每次询问给出两个值 W 、 V ，小军要选取 n 个瓜的子集，使总重量 Ew ≤ W ，总成熟度 Ev ≥ V ，求∑ g 的最大值

[5710xIa]

图14-19内，因为找到记录被剪掉的dp[1,10]是不是不太合理？
就图上来看，也应该是保留物品3和物品1价值更高把？

[krahets]

这里剪枝 dp[1,10] 不是不计入它的结果，而只是不用去递归计算它，因为我们可以从 mem 中直接拿到结果。

    # 若已有记录，则直接返回
    if mem[i][c] != -1:
        return mem[i][c]

[Ryan-BetterMe]

老师，这个我其实不是很理解这个思路。

因为动态规划按照之前的描述应该是从低到顶的计算过程。

所以 dp[i][j] 的描述中是不是要换一种思路好一些：i 表明当前编号物品的选择，j 表明当前容量的大小

也就是说是从 0 -> cap 的遍历过程，如果 j 理解为剩余容量，不是很理解，求老师解惑

[krahets]

复习一下状态定义：前 $i$ 个物品在剩余容量为 $c$ 的背包中的最大价值，记为 $dp[i, c]$ 。
换句话说，给定一个容量为 $c$ 的背包，和前 $i$ 个物品，那么能达到的最大价值为 $dp[i, c]$ 。

这样 $0 \rightarrow cap$ 是否好理解了？这个过程是在计算随着背包增大的过程中，最大价值增大的情况。

[Ryan-BetterMe]

这样转换一下确实好理解了

[Fruit-loops]

这里的描述确实很容易让人迷惑，c想表示的含义其实为“当前选择物品占用的容量”。但是如果使用“剩余容量”，那么很容易让初学者理解为，选择放入物品以后，剩余容量应该是减小的。但是状态转移公式的表示中，放入物品以后，c是增大的。

[krahets]

@Fruit-loops Hi，文中一开始从子问题分解的角度提出：“不放入背包，背包容量不变；放入背包，背包容量减小” ，从而有了“剩余容量”这个概念。c 表示的就是剩余容量，dp[i, c] 代表“当背包还剩 c 容量时，用前 i 个物品能装进的最大价值”。

这里的关键是把 [i, c] 理解为“状态”，我们通过一系列决策来实现状态之间的转移：

• 可以发现，在暴力搜索和记忆化搜索方法中，“剩余容量”是很贴切的，每当做出一个决策，背包的“剩余容量”都在减小。
• 然而，在正向递推中，当我们放入一个物品时，物品总重量 c 增大，这个物品总重量其实就是一开始讨论的“剩余背包容量”，只是由于方向相反，导致“剩余”这个词产生了歧义。

个人建议从子问题分解的角度分析动态规划、进行状态定义，从而推导出状态转移方程。

[hsuan9027]

图14-20的<12>两个箭头颜色是不是反了？

[krahets]

感觉没有

[Rh0-aias]

总结：

定义 dp[n][m] 为背包容量为m时，考虑前n个物品的放入取舍后对应的最大总价值。
当m=0时，dp[][0]=0，因为背包容量为零装不下任何物品。
当n=0时，dp[0][]=0，因为没有任何物品需要考虑是否放入。
以上两个即为边界条件。目标是求n=3，m=4的最大总价值，即dp[3][4]。

由于每个物品要么放入，要么不放入，只有两种可能，那么找出状态转移方程的思路就很自然了：
因为要想知道dp[m][n]，无非是在以下两种情况中取舍：

(A) 在决定完前m-1个物品是否放入后，第m个物品放进了背包里。
(B) 在决定完前m-1个物品是否放入后，第m个物品没有放进了背包里。

对于第一种情况，显然总价值就等于在决定完前m-1个物品是否放入后的最大价值直接加上第m个物品的价值val(m-1)。并且由于放进了物品m，可知在放入第m个物品前的状态对应的容量为n-wgt[m-1]，即：
Val_A=dp[m-1][n-wgt[m-1]]+val(m-1)

对于第二种情况，物品m没有放进去，那么总价值不变，容量不变，即
Val_B=dp[m-1,n]

于是最大总价值就是在两种结果中取较大值dp[m][n]=max(Val_A,Val_B)。于是状态转移方程为：
dp[m][n]=max(dp[m-1][n-wgt[m-1]]+val(m-1),dp[m-1,n])

需要特别注意的是:

(1) 由于要保证物品m能放进去，还得保证n-wgt[m-1]>=0，否则物品m并不能被放进，从而可以直接得出dp[m][n]=dp[m-1][n]=val_2。

(2) 显然背包的容量越大，我们能获得的最大价值也就越高。这也就是为什么在Val_A中，对于dp[m-1]这个状态赋予的容量是n-wgt[m-1]，而不是其他更小的容量。当然，赋予比n-wgt[m-1]更大的容量可能会得到更大值，但就没法把物品m再放进去了。同理，在Val_B中，由于没有放物品m进去，我们赋予状态dp[m-1]的最大容量就是n，这样才能获得最大价值dp[m][n]。

[dxu104]

显然背包的容量越大，我们能获得的最大价值也就越高。这也就是为什么在Val_A中，对于dp[m-1]这个状态赋予的容量是n-wgt[m-1]，而不是其他更小的容量。当然，赋予比n-wgt[m-1]更大的容量可能会得到更大值，但就没法把物品m再放进去了。同理，在Val_B中，由于没有放物品m进去，我们赋予状态dp[m-1]的最大容量就是n，这样才能获得最大价值dp[m][n]。

写好很好！上面是非常重要的点，一定要理解这些内容！d[i,j]中j的位置一定要尽可能的大

[huccihuang]

「剩余容量」这个表述理解了好久，不知道是放完 i 物品后剩余，还是轮到 i 物品的时候背包剩余的量，直接转换为背包容量感觉好理解很多

[krahets]

是的，可以直接理解为“背包容量”。它是个“状态”，和“动作”没有关系。

[panda-on]

是的，后来我也是直接把他理解为当前背包的容量，然后就想清楚了；把他作为子问题看待：即当前背包容量下的最大物品价值

[naivewolf-git]

对于倒序遍历，我是这样理解的：每一次循环本质是利用积累的数据计算当前状态并保存当前状态作为下一行计算的依据，倒序遍历在完成状态计算后更新当前状态并不影响后续遍历的计算，因为后续遍历的cap小所以用不到当前数据，对于优化后的数组来说，相当于在首部保存上一行的价值，在尾部保存当前行的价值。

另外，如果容量是浮点数，是不是需要计算出任意一个或多个wgt相加的组合结果，其元素的有序列表作为cap的遍历范围？

[naivewolf-git]

不对，如何要做组合就不需要动态规划了，感觉还是同一单位就好了🙈

[chenfeicqq]

提个建议：不同配图中的 物品 价值、重量 统一下，初学者更好理解

[Criskly]

在i等于1时，随着c的增加，为什么最大df还是等于5，不是应该变成11 ，16吗，求解答

[Criskly]

这里i是对i物品是否放入的判断

[lewizheng]

你注意一下前面的定义，前i个物品在剩余容量为c的背包中的最大价值，按照你这个情况就是前1个物品（第一个物品），在容量为c的背包的最大价值，那么不管是多少容量，都只能放一个，所以都是5

[noobcodemaker]

k神，我有一个问题，就是在二维数组的动态规划过程中，两个for循环的先后顺序更改后并不影响结果，但为什么空间优化后的动态规划，改变两个for循环的先后顺序，结果就不对了呢

[krahets]

理解这里的核心是：当计算下一个状态的解时，上一个状态的解是否是正确的（是否由于遍历顺序不合理，被覆盖了）？

[peng-yq]

请问背包问题中物品的重量一般都是像10，20，30（背包容量对应10的整数倍）或者1，2，3，（背包容量对应1的整数倍），并且是有序的吗？

[krahets]

Hi～不是的，可以是任意正整数，也不需要有序

[peng-yq]

Hi～不是的，可以是任意正整数，也不需要有序
谢谢回复，已经理解了

[caolib]

使用动态规划得到最大值后，我想知道最好的解决方案(选择那些物品)是什么，求一个反向推导出最佳方案的办法

[dxu104]

gpt关于正序倒序的理解：• 正序遍历：如果从左到右更新数组，那么在计算 dp[j] 时，dp[j - weight[i]] 可能已经被更新为当前行的值，这意味着我们失去了原本的 dp[i - 1][j - weight[i]] 值，导致错误。
• 倒序遍历：如果从右到左更新数组，即从大到小更新 j，那么在计算 dp[j] 时，dp[j - weight[i]] 仍然是前一行的值，因为它还没有被更新。这样就可以正确地进行状态转移。

我自己消化后的理解： 如果你正序的话，我本来是想用上一层的值，例如dp[j - weight[i]] 但是因为正序，你就把dp[j - weight[i]] 这个位置的值给更新的当前行的值，这意味着我们失去了原本的 dp[i - 1][j - weight[i]] 值，导致错误

[SoftwareEngineerPalace]

由此可得状态定义：当前物品编号 i 和剩余背包容量 c, 记为 [i, c]

这个 c 指的把 0 ~ i 这些物品放到背包里后，背包的剩余空间大小吗

[SoftwareEngineerPalace]

还是把第 i 个物品放到背包前，背包的剩余空间 ？

[SoftwareEngineerPalace]

还是把前 i 个物品放进容量是 c 的背包 ？

[SoftwareEngineerPalace]

知道了，指的是把 0 ~ i 这些物品选择性的放进容量是 c 的背包中

[SoftwareEngineerPalace]

为什么要有这行： if (wgt[i - 1] <= c)
不要也行吧

[InvisibleCeylan]

物品重量不能大于背包容量，而且你不加这行dp[c - wgt[i - 1]]在这种情况下会直接出现数组越界读的情况。

[dxu104]

K神，有没有LC 494目标和的题解，看了很多教程还是不是很明白

[krahets]

没有噢～

[SHENLAN-Li]

”当我们做出物品 i的决策后，剩余的是前i-1 个物品的决策“。这句话我读着实在不理解。前面不是有说过DP是一种自底向上吗，也就是由子问题的解构建更大子问题的解。
还有就是j-wgt[i-1}文中的解释是放入第i个物品容量减小，意思是第i个物品的决策影响到了前面第i-1个物品的状态么，好怪异啊，不应该是当前状态被下层更小子问题的状态所影响吗

[hpstory]

Hi @SHENLAN-Li ，你可以这么理解，如果不考虑物品i，原问题就变成了前i - 1个物品在限定背包容量下能放入物品的最大价值，最后就变成从物品0开始考虑。dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1])这个状态转移其实说明了第i个物品的决策受到了前面第i-1个物品的状态影响。

[Danbor86]

大大您好，我想请问，在记忆化搜索的代码中，当超重时，是不是应该写成

if wgt[i - 1] > c:
mem[i][c] = knapsack_dfs_mem(wgt, val, mem, i - 1, c)
return mem[i][c]

来避免超重时再次向下递一次，谢谢！

[krahets]

都可以的～

[2419174660]

𝑑𝑝[𝑖, 𝑐] = max(𝑑𝑝[𝑖 − 1, 𝑐], 𝑑𝑝[𝑖 − 1, 𝑐 − 𝑤𝑔𝑡[𝑖 − 1]] + 𝑣𝑎𝑙[𝑖 − 1]) 这个递推公式是不是应该说明后面那个c不等于前面那个c，否则会误导人

[2419174660]

或者说明是在加重量，而不是减重量

[krahets]

这个公式里的所有 c 都为同一个变量（都相等）

[Temmp1e]

为什么无剩余背包容量的时候最大价值也是0

[xuanxuanxie]

这里的价值应该指的是加入当前状态的价值，因为加不了东西了，所以价值为0，或者理解为剪枝了（？）

[Temmp1e]

"前 i 个物品在剩余容量为 c 的背包中的最大价值" 我感觉这句话很容易让人理解产生偏差，应该直接说 前 i 个物品在容量为 c 的背包中的最大价值，如果加个剩余好像就再说一个多少容量的背包已经装了多少，然后剩余多少，在已经装了的里面的最大值。我当时这么理解就错了（可能是我语文不好www，如果有跟我一样理解差错的及时纠正就行）

[a2635814919]

我感觉图14-19的 dp[2,10] 左子树与其说是剪掉，不如说是因为之前已经计算过了所以简化运算，直接引用，图里面修改成 dp[2,10] 指向 dp[1,10] 是不是更好一些

[kevinyangff]

状态参数c的意义是否应该是背包空间已使用量，而不应该是背包空间剩余量？

[kevinyangff]

哦，我想错了，应该是都可以，状态参数的意义与思维过程有关系。
i表示第几轮选择、c表示背包空间使用量
i表示物品编号、c表示背包空间剩余量
这两组意义可以推导出同样的状态转移顺序

[krahets]

Hi，其实直接理解为“背包容量”即可，它代表的是一个“状态”。dp[i, c] 的含义是：给定前 i 个物品和一个容量为 c 的背包，能得到的最大价值是多少。

文中用“剩余容量”与暴力搜索和记忆化搜索对应。在搜索过程中，我们每考虑一个物品的选择，剩余背包容量不变或减小。

[Knight-wh]

起初看背包问题的时候感觉很反直觉，当i-1轮时加入背包时，直觉上觉得这是个具有后效性的问题。反复看了几遍之后发现，c-wgt[i-1] 这个操作就已经避免了超出背包容量的情况

[Knight-wh]

嗯嗯是的

[echo1937]

花了很久才看明白dp表（说明有点短），推荐这个视频：https://www.bilibili.com/video/BV1pY4y1J7na/

[RightNode]

“对于每个物品来说，不放入背包，背包容量不变；放入背包，背包容量减小。由此可得状态定义：当前物品编号i和剩余背包容量c，记为[i，c]。”

个人觉得这段话中的“剩余背包容量c”很容易造成歧义，以为是放置了物品i(或前i个物品)后，背包还剩下容量c，但实际这里指的是用容量c去装前i个物品。比如下文不远处的dp[n, cap]，当时在读的时候就理解成“前n个物品在剩余容量cap中的最大价值”，感觉有点别扭，那背包总容量岂不是“cap+sum(前n个物品的重量)”？dp[i,c]的解释改为“用容量c去装前i个物品的最大价值”则没有歧义。

[krahets]

在暴力搜索和记忆化搜索方法中，我们采用子问题分解的方式分析问题，决策是按照物品编号的倒序执行的。状态定义中的“剩余容量”指的是放置第 i 个物品后背包的剩余容量 c 。 因此，在从顶至底的搜索方法中，“剩余容量”这个表述是贴切的。

然而，递推方法（迭代）和搜索方法（递归）的方向相反，导致“剩余”的含义也出现翻转。这是你提到的歧义的来源。但需要注意的是，递推方法并不适合被理解为正序决策的过程，而是状态转移的过程，因此没有“放置了物品 i (或前 i 个物品)后”的概念。具体来看：

• 搜索（从顶至底）的方法可以视作在一个决策树上从根节点到叶节点的遍历，每条从根到叶的路径代表一个具体的决策序列。
• 递推（从底至顶）的方法则是填充一个状态表，逐格确定最优解，其过程本身不直接表现为一个明确的决策序列。

看到了几位同学都在反映对“剩余容量”的疑惑。我将优化这处表述，谢谢反馈！

[hanzhih]

for (int c = cap; c >= wgt[i-1]; c--)
{
dp[c] = myMax(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
}
这样写是不是降低了时间复杂度？

[TapTapLucas]

注意，文中说的前i-1和代码中[i-1]是不同的意思：
在说明物品为第i个时，物品从1开始计数。
前i-1是指考虑是否将第i个物品放入背包时，关注的前面的 i－1个物品，指的是问题中的一组物品。
而[i-1]作为数组索引，由于索引是从0开始的，所以第i个物品的重量和价值在数组中为i-1，是实际数组中的索引。

如有表述错误请指正。