背包 DP

[Ir1d]

https://oi-wiki.org/dp/backpack/

[yizimi-yuanxin]

还没补完吗？

[Ir1d]

@yizimi-yuanxin 是哒，路漫漫其修远兮，大佬有没有兴趣参与其中

[2158454657]

为什么不用数组来表示，Fi,w 这样的表达有些模糊，不好理解

[SteveTaizhou]

因为这是 $\LaTeX$ 不是代码

[lewis666a]

$\LaTeX$ 下表示数组就是这么表示的

[yellow-mt]

对，是$F_{i,w}$

[caohongchuan]

01背包的核心代码为何看不懂，，，

[upupming]

感觉讲解的很简洁，有一点难以理解，希望扩充一下~

[tnoonkyk]

大师，我悟了！

[yxr-yolanda]

优化的地方打错了吧...

[Supremacy-power]

真不错

[woshixjk]

赞，真心不错

[Jebearssica]

输出方案那一小节是不是有点问题, v代表的是背包容量, 下面的代码应该是减掉第 i 项物品的重量吧?

  if (g[i][v]) {
    选了第 i 项物品;
    v -= 第 i 项物品的价值;

[dst111dst]

还有小数背包呀？

[Maxpicca-Li]

感觉多重背包是不是讲复杂了？感觉可以实现 $O(nW)$ 的算法，如下代码，不知道对不对:

for (int i = 1; i <= n; i++)
    int cnt = 0; // 选择的次数
    for (int l = w[i]; l <= W; l++)
        if (f[l - w[i]] + v[i] > f[l] && cnt<k[i]) {
            f[l] = f[l - w[i]] + v[i];  // 核心状态方程
            cnt++;
        }

[Master-Q-i-a-n]

不太对吧

[niu-zh]

不太对吧

[GoodGoodProgram]

不对，这是完全背包，重复了装k个相同的物品

[alphagocc]

@Maxpicca-Li 你再想想？

[Randywang080303]

好难😭

[taojunhui]

背包问题，其实就是在约束条件下，求极大问题，我理解的对吗。

[LiqueurChoc]

很简洁清楚谢谢大哥(^o^)/

[codercmh]

dp好难

[zhouxuanhong]

完全背包-过程
f[i][j-w[i]]不可能由f[i][j-w[i]*2]转移吧
应该是f[i-1][j-w[i]*2]才对，所以转移方程就错了？
那个i应该是i-1?