> For the complete documentation index, see [llms.txt](https://nataliekung.gitbook.io/ladder_code/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://nataliekung.gitbook.io/ladder_code/bei-bao-wen-ti.md).

# 背包问题

01背包

二维数组可以优化成一维数组，V倒序

因为f\[i]\[v]=max{f\[i-1]\[v],f\[i-1]\[v-c\[i]]+w\[i]}变成

```
for i=1..N
    for v=V..0
        f[v]=max{f[v],f[v-c[i]]+w[i]};
```

这里大V由小的V得出，不先算出来大的，先算小的话，将来算大的用到的小的，是被更新过的f\[i]不是f\[i-1]

01背包初始化

要求恰好装满背包，那么在初始化时除了f\[0]为0其它f\[1..V]均设为-∞，这样就可以保证最终得到的f\[N]是一种恰好装满背包的最优解。

如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将f\[0..V]全部设为0。