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；

[krahets]

这个状态转移问题是不是不太对，请再确认一下。你说的这个问题本文也讲了，可以看看

[likz1994]

谢谢老师

[Rh0-aias]

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

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

[sxf1234]

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

[krahets]

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

[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 时，才只能得出结论：必须不选该硬币。

[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

[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背包的规则。

如有不对请指正。