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]

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

[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 个物品)后”的概念。具体来看：

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

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

[LiHuigui]

很对很对！我天！你这句dp[i,c]是“用容量c去装前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，是实际数组中的索引。

如有表述错误请指正。

[SEELE0]

简短点说感觉可以理解成就是二维数组 第一行 第一列 全填 0
也就是第i个物品 就对应 第i 个索引 所以当要寻找上一次的结果时就是 找 第i-1个物品。
而一维数组没有这个边界状态操作 所以需要匹配到正确的索引也就是i-1 索引 代表 第i个物品的重量和价值

[liuc7721]

定義要弄清楚：dp[i][w] 的 i 通常表示我們正在考慮的前 i 個物品（這裡 i 是第 i 個物品，而不是數組中的下標）。

換個方式解釋，dp[0]代表沒選任何物品的最大價值，但是weights[0]代表第一個物品的重量，而非沒選物品的重量!

[Natural-selection1]

在python下暴力搜索反而是时间最短的,是因为数据量不够大么?

[RRRROBOT]

python 好像有cache机制 导致部分计算的过的值 存储起来了
当然 你也可以理解为 数据量不够大

[wenboxu888]

为什么空间优化的时候采用正向遍历会出现覆盖问题，而倒序遍历不会

[gonisan]

因为在遍历本行时，dp数据实际存储的是上一行的状态，如果j正向遍历的话，dp数组下标小的会优先被覆盖，进而影响了本行后续数据的计算，因为本行数据依赖于上一行数据，举例就是dp[0]被覆盖了，但是后续的dp[1]都计算还依赖于dp[0]；倒序不会出现这个问题是因为倒序的话是dp数组中下标最大的先被覆盖，本行数据计算时下标较小的不依赖于较大的

[a2635814919]

有没有覆盖问题是取决于最小子问题的结构的。以矩阵的格子作为不同状态：        假如 s[i][j] 跟 s[i - 1][j] 和 s[i - 1][j - 1] 有关，即当前格子的左侧和左上，则压缩空间时正序遍历无法获取左上的格子历史信息。        同理，s[i][j] 跟 s[i - 1][j] 和 s[i][j - 1] 和 s[i - 1][j - 1]有关，即左侧，正上，左上，压缩空间时正序遍历也会丢失左上格子历史信息。

[Blueman123456]

// 状态转移
for (int i = 1; i <= n; i++) {
for (int c = 1; c <= cap; c++) {
if (wgt[i - 1] > c) {
// 若超过背包容量，则不选物品 i
dp[i][c] = dp[i - 1][c];
} else {
// 不选和选物品 i 这两种方案的较大值
dp[i][c] = myMax(dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] + val[i - 1]);
}
}
}
这样写会越界呀，[c-wgt[i-1]]，会小于0

[Blueman123456]

撤回哈哈

[mcbegin]

dp[i][c] = max(dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] + val[i - 1]);
这一句中应该是加 val[i] 吧，而不是val[i-1]？

[mcbegin]

还有 c - wgt[i]

[769174850]

指的是上一个的操作，就是i-1

[PACRian]

因为作者这里定义的wgt[i-1]和val[i-1]就是第i个物品(题目描述，从1计数)的重量和价值，与之对应的作者给的dp表的行也是从1开始(当然要先有dp = [0] * (cap + 1)的初始化)。我都按从0开始计数，也可以：

[PACRian]

def solve_01_package(wgt, val, volume):
item_nums = len(wgt)
dp = [0]*(volume+1)

for i in range(item_nums):
    for j in range(1, volume-wgt[i]+2):
        # 注意：按逆序遍历
        dp[-j] = max(dp[-j], dp[-j-wgt[i]] + val[i])

return dp[-1]

[Bo-Teng]

我觉得是因为i的起始值是1而重量数组和价值数组起始是0

[ruihao-yan]

画的真是太好了👍

[bitWatcher]

为了便于理解， 建议作者将物品编号也从0 开始。
有些读者没有注意到数组索引开始位和物品编号开始位是不一样的。

另外物品编号从1开始设计， 反而让代码变得不好读

[LiHuigui]

我反而觉得作者这样更好读。。

[syutengu]

没办法，dp表中的0行0列分别是用来表示没有物品和没有容量的初始状态的。
不用这个方法表示，代码写起来应该也不会舒服很多。

[syutengu]

空间优化这段里，
按Z字形写入想象的dp表（实际已压缩为dp行），就会导致左上方的dp[c-wgt[i-1]]这个数据被覆盖；
按左右镜像Z字形（即顺序遍历行，但逆序遍历列）更新，就推迟了这个数据被覆盖的时机。
这是一个非常具有普遍意义的空间优化手法吧。

[syutengu]

      for (let c = cap; c > 0; c--) {
        if (wgt[i - 1] <= c) dp[c] = Math.max(dp[c], dp[c - wgt[i - 1]] + val[i - 1])
      }

简写成以下形式，应该不会影响结果吧。

      for (let c = cap; c >= wgt[i - 1]; c--) {
        dp[c] = Math.max(dp[c], dp[c - wgt[i - 1]] + val[i - 1])
      }

[Ares-bit]

“如果采取正序遍历，那么遍历到 时，左上方 值可能已经被覆盖，此时就无法得到正确的状态转移结果。“
请问这句话怎么理解？正序遍历到dp[i][j]的时候，数组中存储的dp[i-1]行状态已经是算好的，固定不变的了，为什么会被覆盖掉？

[Ares-bit]

想明白了
//必须倒序遍历，因为就这一个数组，里面存储的是上次的状态，你边用还得边写你本轮的数据进去
//如果正序遍历的话，你算到后边，就可能把前边的数据改写成本轮的，然后你本轮的就算错了
//如果倒序遍历的话，后边用完改写后，往前走可以保证不会再用后边的状态，所以不会影响

[LUFEE666]

上面有地方写错了
第二步：找出最优子结构，进而推导出状态转移方程里在讨论放入物品i，不应该是容量减少w[i]，价值增加v[i]，而不是i-1

[MoRongsi]

在上面逆序思考的过程中，对于物品i，放不放入指的是物品i放入，前一个物品剩余可用的背包容量，所以是容量减少w[i-1]（物品序号是i，i的重量是w[i-1]）。这里和正序思考的过程不同。可以往下翻翻，下面有详细解答。

[surpoloyang]

图14.20的step12画错了，应该是$dp[i-1, c]$更大