很经典的动态规划问题，具体思路这里就不列出了，网上太多资料了。想要详细理解的话可以去看背包九讲
这里分别列出，01背包，完全背包，部分背包 golang实现。
01背包
给定 n 种物品和一个容量为 C 的背包，物品 i 的重量是 wi，其价值为 vi 。
应该如何选择装入背包的物品，使得装入背包中的物品的总价值最大？
从左往右，从上往下填表（example： 5表示重量，12表示价值）
1.png
代码and注释
dp[i][j] = max(dp[i-1][j], nums[i][1]+dp[i-1][j-nums[i][0]]) 仔细想清楚这一行
backpack.png
完全背包
给定 n 种物品和一个容量为 C 的背包，物品 i 的重量是 wi，其价值为 vi，每个物品都有无限多件，现在往背包里面装东西，怎么装能使背包的内物品价值最大？
先看图：
这是一个一维数组，每一行表示每次遍历的结果
2.png
代码and注释，理解上面一个，这个也很好理解
backpack1.png
部分背包
给定 n 种物品和一个容量为 C 的背包，物品 i 的重量是 wi，其价值为 vi，每个物品都有ki件，现在往背包里面装东西，怎么装能使背包的内物品价值最大？
一个比较简单但是效率不高的方法： 把物品i的ki件物品转化为k件不同的物品，直接就转化为01背包问题了。不过效率较低。
另一种思路：再申请一个数组来保存物品i的使用个数，从而控制物品i的数量,用完全背包的思路解决问题
代码and注释
backpack3.png
遍历过程：dp表示每遍历一个物品时的最优价值，count表示重量为n时放入物品i的个数
dp[0 0 0 0 0 8 8 8 8 8 16 16 16 16 16 16]
count[0 0 0 0 0 1 1 1 1 1 2 2 2 2 2 2]
dp[0 0 0 0 3 8 8 8 8 11 16 16 16 16 19 19]
count[0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1]
dp[0 0 0 0 3 8 8 10 10 11 16 16 18 18 20 20]
count[0 0 0 0 0 0 0 1 1 0 0 0 1 1 2 2]
dp[0 0 3 3 6 8 9 11 11 14 16 17 19 19 22 22]
count[0 0 1 1 2 0 3 1 1 2 0 3 1 1 2 2]
dp[0 0 3 3 6 8 9 11 11 14 16 17 19 19 22 22]
count[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
总结：
基本上背包问题的解题思路最终都会转化为01背包问题，核心代码都是基于一个公式：
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
代码还有很大优化空间。只是记录一下自己的学习过程。
网友评论