目录
01背包
完全背包
总结
背包问题算是动态规划的经典问题了,一定要记住动规五部曲
1.定义dp数组
2.确定递推公式
3.初始化
4.确定遍历顺序
5.验证
01背包
关于01背包就是给定背包的容量和每个的物品价值,一个物品只能放一次,求背包的最大价值
dp[i][j]表示从前i个物品里任取放入背包大小为j的最大价值为dp[i][j]
01背包的递推公式:dp[i][j]=Math.max(dp[i-1][j],dp[i-weight(i)]+values[i])
初始化:dp[0]=0
遍历顺序:先遍历物品或者遍历背包都可以
一维dp数组只能先遍历物品后遍历背包,且背包的遍历顺序是倒序
完全背包
关于完全背包就是给定背包的容量和每个的物品价值,一个物品可以放无数次,求背包的最大价值
dp[i][j]表示从前i个物品里任取放入背包大小为j的最大价值为dp[i][j]
01背包的递推公式:dp[i][j]=Math.max(dp[i-1][j],dp[i-weight(i)]+values[i])
初始化:dp[0]=0
遍历顺序:先遍历物品和先遍历背包都可以,都是正序
如果求组合数就是外层for循环遍历物品,内层for遍历背包。
如果求排列数就是外层for遍历背包,内层for循环遍历物品。
总结
问能否装满背包,或者最大价值是多少
dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i])
问装满背包有几种方法(几种组合)
dp[j]+=dp[j-nums[i]]
问装满背包的最少物品
dp[j]=Math.min(dp[j],dp[j-nums[i]]+1) 初始化为最大值 dp[0]=0