很经典的动态规划问题,具体思路这里就不列出了,网上太多资料了。想要详细理解的话可以去看背包九讲
这里分别列出,01背包,完全背包,部分背包 golang实现。
01背包
给定 n 种物品和一个容量为 C 的背包,物品 i 的重量是 wi,其价值为 vi 。
应该如何选择装入背包的物品,使得装入背包中的物品的总价值最大?
从左往右,从上往下填表(example: 5表示重量,12表示价值)
代码and注释
dp[i][j] = max(dp[i-1][j], nums[i][1]+dp[i-1][j-nums[i][0]]) 仔细想清楚这一行
完全背包
给定 n 种物品和一个容量为 C 的背包,物品 i 的重量是 wi,其价值为 vi,每个物品都有无限多件,现在往背包里面装东西,怎么装能使背包的内物品价值最大?
先看图:
这是一个一维数组,每一行表示每次遍历的结果
代码and注释,理解上面一个,这个也很好理解
部分背包
给定 n 种物品和一个容量为 C 的背包,物品 i 的重量是 wi,其价值为 vi,每个物品都有ki件,现在往背包里面装东西,怎么装能使背包的内物品价值最大?
一个比较简单但是效率不高的方法: 把物品i的ki件物品转化为k件不同的物品,直接就转化为01背包问题了。不过效率较低。
另一种思路:再申请一个数组来保存物品i的使用个数,从而控制物品i的数量,用完全背包的思路解决问题
代码and注释
遍历过程: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]}
代码还有很大优化空间。只是记录一下自己的学习过程。
有疑问加站长微信联系(非本文作者)