chapter_dynamic_programming/unbounded_knapsack_problem/

[giscus[bot]]

chapter_dynamic_programming/unbounded_knapsack_problem/

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

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

[likz1994]

老师 您好，想请教下，在LeetCode上有个：可以凑成总金额所需的 最少的硬币个数 问题，它动态方程为：
dp[i][a] = Math.min(dp[i - 1][a] , dp[i][a - coins[i - 1]]) +1。想问下 最后为什么要 +1；

[likz1994]

谢谢老师

[Junyu-Tang]

对于完全背包的问题，感觉似乎可以这样做：
先求出每个物品的平均价值=value/weigh。
在可以重复选取的情况下，先最大可能的放入最大平均价值的物品。
然后在能放进去的前提下，尽可能放进次最大平均价值的物品放。
如果放不下，就接着考虑次次最大平均值的物品，以此类推...

比如例子中的平均价值为：
苹果：5
香蕉：6
葡萄：5
菠萝：5.25
西瓜：4.8
于是我们要尽可能的多放香蕉（两个），接着考虑菠萝，再接着考虑苹果或者葡萄，但是剩下的容量不能够放进葡萄和菠萝，所以最后只能再放一个放苹果...

[sxf1234]

这个就是后面讲的贪心算法了

[krahets]

@Rh0-aias 完全背包使用这种解法可能会无法得到最优解。可以看一下贪心算法章节中找零钱的例子。

[sinabs]

这地方写错了吧, 应该先给min第二个参数+1,在min

[muzishuiji]

哈喽，老师，想请教下

当目标金额为 
0时，无须选择任何硬币即可凑出目标金额，因此应将首列所有 dp[i][0]
 都初始化为 1
 

总金额为0，感觉应该是没有组合能凑出来，这个1的意思是是空组合吗？

[krahets]

是的，“没有硬币”也可以被视作一种方案

[HustRobb]

零钱兑换问题：优化主体是硬币数量而非商品价值，因此在选中硬币时执行+1即可
为什么选择加一就行啊，问题不是说每种硬币可以重复选取吗

[krahets]

Hi，每次选择都是选择 $1$ 枚硬币。能否重复选取体现在状态转移上，建议对比一下“0-1 背包”和“完全背包”的转移方程的区别

[Peng0100]

感觉可以增加下：背包类问题的物品和背包遍历的先后性

[RRZXX]

老师，编辑距离问题的时候，步数是要+1的，这里为什么不用+1？

[krahets]

Hi，编辑距离的“步数”对应的是背包问题的“物品总价值”，因此我们不用 +1 ，而是 +物品价值

[RRZXX]

coins[i - 1] > a 为什么不是 coins[i - 1] != a 呢？恰巧能凑出来金额a的值，才能选择用不选择当前硬币+选择当前硬币的吗？

[krahets]

Hi，这是因为只有在硬币面值 coins[i-1] 超出剩余金额 a 时，才只能得出结论：必须不选该硬币。

[zzy1661]

比如零钱[2,3]，要凑出目标金额3，需要的最小数量，
在dp方程中会计算：前1个硬币凑出3需要的数量，该数量取决于“前0个硬币凑出3的最小数量”和“前1个硬币凑出1的最小数量+1” 中的最小值，前者是max，后者由于coins[i - 1] > a，变成“前0个硬币凑出1的最小数量“，也是max。也就是表明凑不出来。

凑不出来的场景，因为硬币数量无限，一定会出现当前硬币值>目标金额的场景（往前越减越少），即得到max值。

[zaipingy]

coin_change_ii.rs代码中有个注释copy过来是错的

for i in 1..=n {
        for a in 1..=amt {
            if coins[i - 1] > a as i32 {
                // 若超过目标金额，则不选硬币 i
                dp[i][a] = dp[i - 1][a];
            } else {
                // 不选和选硬币 i 这两种方案的较小值 （应该是  不选和旋硬币 这两种方案之和）
                dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1] as usize];
            }
        }
    }

[night-cruise]

提了个 pr 修复了：#1027

[anxiaochou]

那零钱兑换问题II能不能用类似爬楼梯的思想呢？面值就是爬的步数，target就是层数。

[SoftwareEngineerPalace]

感觉思想是可以的，就是硬币的种类太多的话，代码的时间复杂度会不会特别高

[SoftwareEngineerPalace]

还不如用回溯

[55guozi]

作者能否再讲一个背包问题前k优解的问题，我看别人的代码有点看不懂

[krahets]

mark

[an7tang]

同求！谢谢作者

[Fulin-Gao]

如果最小面值是0.5元，amt+1就不是MAX

[krahets]

是的，此时为 2 * amt + 1

[sunshinesDL]

所以可以考虑题干上再加一个条件：硬币最小面额为 1。

[2022241104]

请问对于零钱兑换问题的空间优化为什么要dp = [MAX] * (amt + 1)呢

[Krys1215]

零钱兑换问题2；
为什么当前状态的组合数量等于不选当前硬币与选当前硬币这两种决策的组合数量之和呢？
我不是很理解，相当于是说：用1块和2块硬币凑到5块的组合个数 = 用1块硬币凑到5块的组合个数 + 用1块和2块硬币凑到3块的组合个数。
对吗？

[krahets]

是的。准确说是：前 i - 1 种硬币能够凑出金额 a 的组合数量 + 前 i 种硬币能够凑出金额 a - coins[i-1] 的组合数量，在这里 i = 2 , a = 5

[Keria04]

##关于背包问题的遍历顺序有着疑问
1.为什么完全背包问题先遍历背包再遍历物品就是求组合数，先遍历物品再遍历背包就是求排列数
2.为什么0-1背包问题是先遍历物品再遍历背包，如果先遍历背包再遍历物品会如何？

[Serendipity-zyf]

1、第一个问题是不是说反了？应该是完全背包问题先遍历物品再遍历背包就是求组合数，先遍历背包再遍历物品就是求排列数
2、如果采用二维数组来 dp 的话，是没有区别的，相当于一种是按照列更新，一种是按照行更新；但一维的话要注意倒序遍历容量，防止出现重复使用物品

[Keria04]

第一个问题确实说反了，自己这边也想明白了，但是第二个问题还是没懂。

[TapTapLucas]

对于第二个问题，如果先遍历背包再遍历物品。那么对于每一个背包容量，都需要依次考虑每个物品是否放入，于是导致出现一种情况：在处理一个较大容量的背包时，当前物品可能会被多次考虑（因为每个容量都重新遍历所有物品），本质上转变成了一个完全背包问题的处理方式，即物品可以被多次选择，这与0-1背包问题的要求冲突。

在0-1背包问题中，先遍历物品再遍历背包，确保每个物品只被计算一次，可以保持决策的不可逆性。
举个例子，物品A 重量1价值10，物品B 重量1价值20。
先遍历容量为1的背包会出现：
考虑A，可放入，dp[1] = 10；
考虑B，可放入，dp[1] = 20；
可见此时B的决策覆盖了A的决策产生的价值，当背包更大时，重复相同物品的决策就违反了01背包的规则。

如有不对请指正。

[HertzTon]

“在 0-1 背包问题中，每种物品只有一个，因此将物品放入背包后，只能从前i-1个物品中选择。
在完全背包问题中，每种物品的数量是无限的，因此将物品放入背包后，仍可以从前i个物品中选择。”
描述”将物品放入背包后“是否应该是“将物品放入背包前“？想了很久没想明白

[HertzTon]

就是说假设要放入，完全背包问题下前i个物品的最大价值状态可以从更小背包的前i个物品的最大价值状态转移过来，因为在决定第i个物品放入的前后第i个物品都是可以选择的；而0-1背包只能从更小背包下前i-1个物品的最大价值状态转移过来，因为决定第i个物品放入前只能选择前i-1个物品。

[HertzTon]

目前姑且是理解的

[HertzTon]

打错了，姑且是这么理解的😂

[Rumiple]

原文“将物品i放入背包后，只能从前i-1个物品中选择”，是假设已经选了第i个物品，所以0-1背包问题就只能从前i-1个物品中选择物品放入。
背包问题分析思路是从大容量的物品开始分析的，因为这样可以更好的观察到重叠子问题，但代码实际实现时是从小容量到大容量开始写的。所以原文的描述是先考虑第i个物品，然后再考虑前i-1个物品。

[HertzTon]

感谢回复。原文的这句话两个部分的前后关系是分析当前问题和子问题的顺序，而不是物品放入顺序，这样就可以理解了。

[MaikieMaiky]

关于零钱兑换问题(非动态规划)的实现，我发现了一个潜在的问题，可能会导致在某些情况下无法正确处理无解的情况。

问题出在初始化和返回值判断部分：

1. 初始化时，除了第一行，其他所有元素都被设置为0：

   vector<vector<int>> dp(n + 1, vector<int>(amt + 1, 0));

2. 返回值判断：

return dp[n][amt] != MAX ? dp[n][amt] : -1;

这样的实现会导致一个问题：如果无法凑出指定金额，dp[n][amt] 就不会被覆盖, 其仍为默认值0，而不是 MAX。这会导致函数错误地返回0，而不是-1。

空间优化后的代码不会出现此问题

建议的修改方案：

1. 将初始化改为：

   vector<vector<int>> dp(n + 1, vector<int>(amt + 1, MAX));
   for (int i = 0; i <= n; i++) {
       dp[i][0] = 0;
   }

2. 修改返回值判断：

return dp[n][amt] != MAX ? dp[n][amt] : -1;

这样修改后，当无法凑出指定金额时，dp[n][amt] 将保持为 MAX，函数就能正确返回 -1 表示无解。
这个修改能确保算法在所有情况下都能正确工作，包括无法凑出指定金额的情况。

[MaikieMaiky]

已解决

我提出的问题有误,在遍历过程中,如果凑不出指定值且硬币金额小于目标金额时,他的子问题也是无效解,最终状态转移方程会变成min(MAX, MAX + 1),因此仍然是MAX无效解

[sunshinesDL]

是的，使用前 i 个硬币凑不出目标金额，那么，使用前 i- 1个硬币，也会凑不出，
...（向下递推）
使用前 0 个硬币，凑不出，返回 MAX，
然后层层传递 MAX，直到该问题的解。

[Cover-WU]

本节完全背包问题中，在考虑放入物品i的时候，为什么容量约束是c-wgt[i-1]而非c-wgt[i]？

[Cover-WU]

了解了，因为i是序号i-1

[jungleford]

            if (wgt[i - 1] > c) {
                // 若超过背包容量，则不选物品 i
                dp[c] = dp[c]; // <- ???
            } else {

这行是？

[wLinHoo]

用上一轮的dp直接更新这一轮的

[syutengu]

形式代码，仅为教学用，无实际意义吧。

[Ares-bit]

为什么完全背包的问题中，dp[i][j]只能转移到dp[i-1][j]或dp[i][j-wgt[i-1]]+val[i-1]这两种呢？我理解dp[i-1][j]对应本轮放不下i的情况，dp[i][j-wgt[i-1]]+val[i-1]对应本轮能放下且选了i，并且上一次也选了i的情况，那么为什么不存在dp[i-1][j-wgt[i-1]]+val[i-1]来表示本轮能放下且选了i，并且上一次选了i-1的情况呢？dp[i][j]的状态不应该是从dp[i-1][j]、dp[i][j-wgt[i-1]]+val[i-1]、dp[i-1][j-wgt[i-1]]+val[i-1]这三种中选出的最大值吗？

[lwj2001]

前i - 1 个物品包含在了前 i 个物品的集合内，也就是说dp[i-1][j-wgt[i-1]]+val[i-1]所表示的情景，在dp[i][j-wgt[i-1]]+val[i-1]中已经被全覆盖了

[wdllmh]

这就是要从左往右更新的原因，因为当比较dp[i-1][j-wgt[i-1]] + val[i-1] 和 dp[i][j-wgt[i-1]] + val[i-1]的时候，即比较斜向与横向的箭头时，斜向的已经在左侧更新时保证<=横向的箭头了。

[gopherhiro]

这么学习&理解，感觉DP好简单呀。

[gopherhiro]

在实践的过程中，关键是不好核定边界与状态转移的定义。到底是怎么才能想出来。
特别是状态转移方程的定义，有一种神来之笔的感觉，很神奇！

[sunshinesDL]

可以先定义状态，然后思考当前状态的解，如何由其子问题的解来递推。

[zishuai-hao]

🥹感动了，看完上一章节马上去leetcode刷了一道零钱兑换，没想到这一章还就是这道题

[jceng574]

关于完全背包公式推导的想法

动态规划思想：dp[i,j]是怎么得到的

1，可能是i-1没选，也就是由 **dp[i-1,c]**得到

2,也可能是在i时候没选，也就是dp[i,c]得到（不成立，有了i就代表选过i）

3,可能是在i-1时候选了，也就是dp[i-1,c-wgt[i-1]]+val[i-1]

4也可能是在i时候又选了一次,也就是 dp[i,c-wgt[i-1]]+val[i-1]

​

故最大值只会在1,3,4之间产生

然后3肯定小于4，因为4中多了i这一种

故得到公式

[jceng574]

感觉补充一下会好理解很多

[HansSeven]

稍微提一下我的想法，我用最短路径算法比较多，因此我特别在意对每个节点处取他的最优值。
在本节的问题中：
完全背包问题：感觉可以像接雨水一样，直接计算每个重量的最高价值,递推出最终结果
零钱兑换问题：也可以计算当前存款值的硬币数量最优解
零钱兑换问题2：更简单，直接统计每个存款值的解数量，往后都是直接加的

本质上在我看来就是都类似于跳楼梯，只不过跳的距离choice变多了

那么为什么0-1背包问题不能选择每个重量作为state状态来计算最高价值呢，事实上，我感觉这个特别极限，因为背包问题，如作者一样选择物品索引i或者如我一样选择重量作为state状态都是可以的，但是由于0-1背包问题限定了物品选择，导致在计算state对应的dp数组值的时候，这个递推子任务会受到严重影响，因此选择的是i，不过我算法没那么厉害，我第一眼没有想到用物品索引i作为state

这里因为之前做过接雨水，通过接雨水第一次认识了动态规划。
我感觉动态规划的重点问题是选对state状态，你只有选择正确的state才能得出正确可用的递推公式，像我刚才提出的重量，或是接雨水中的坐标，都是固定不变互相不相关的值，特别好用，也容易想到。