动态规划 背包（dp动态规划中的背包问题01）

今天小编苏苏来为大家解答以上的问题。动态规划 背包，dp动态规划中的背包问题01相信很多小伙伴还不知道,现在让我们一起来看看吧！

1、(1)将二维数组转化为一维数组之后，f[v]表示v的容量最多装多大价值。

2、如果顺序枚举的话，每种物品可能多次使用。

3、例如某个物品重量为5，价值为10，那么就会用f[0]去更新f[5]，用f[5]去更新f[10]，最后出现f[0]=0，f[5]=10，f[10]=20的情况。

4、而这是01背包，要求每种物品只能用一次。

5、逆序枚举时，是在f[5]被f[0]更新之前，就用f[5]更新f[10]，这样就可以保证用一次。

6、(2)首先要搞明白f[i][v]的定义:用前i种物品恰好装满一个容量为v的背包，最大价值是多少。

7、这句话的意思就是说，费用总和为v的状态可能没有意义。

8、譬如说所有物品加在一起的重量都不到v，那么f[N][V]必然没有意义了。

9、只能去找f[N][0..V]中的最大值来输出。

10、但是如果我们改变一下f[i][v]的定义:用前i种物品，在总重不超过v的情况下，最大价值是多少。

11、就可以直接输出f[N][V]了，这样只需要改变一下转移方程，加上一项f[i][v-1]。

12、还有问题请追问。

本文就为大家分享到这里，希望小伙伴们会喜欢。

　　免责声明：本文由用户上传，与本网站立场无关。财经信息仅供读者参考，并不构成投资建议。投资者据此操作，风险自担。 如有侵权请联系删除！