背包问题的本质思路就是决策:放还是不放该物品
一般的解决思路就是贪心思想。
背包的解决方案就是:
1.dfs+回溯
2.动态规划解决
两种都涉及到了决策方案
在dfs内部就是两种搜索:放和不放
在动态规划就是比较最大值再进行更新操作(在一维数组内部可以这样说明),
在二维数组内部,我把这种max(... , ...)叫做表格的填充操作
第一种背包问题:0-1背包
0-1背包就是每一个物品的数量只有一件,有一个固定容量的背包,有数个含有两种属性(价值和体积)的物品,求最大价值此时?
第二种背包问题:完全背包
完全背包与0-1背包问题的唯一区别在于每一个物品的数量都有无限个,求最大价值?
之前,我对这两个问题,尤其是枚举的顺序和这样枚举的意义是理解糊涂的,前几天看了一些资料,更加清晰了。
首先。先来探讨枚举的顺序(第二个循环)问题和这样枚举的意义是什么?
01package:
for(int i=1;i<=n;++I)
for(int j=rongliang;j>=c[i];--j)
dp[j]=max(dp[j],dp[j-c[i]]+w[i]);
因为每一件物品只有一件,如果从第一件物品开始选的话,前面选择的物品一定会影响后面的值。
我们不妨c[i]~rongliang的顺序开始考虑,假如dp[2]的值被更新了,
有因为dp[3]=max(dp[3],dp[3-c[i] ]),而原来的dp[2]的值被改变了,所以dp[3]不一定是最大的值。
mulit_package:
for(int i=1;i<=n;++I)
for(int j=c[i];j<=rongliang;++j)
dp[j]=max(dp[j],dp[j-c[i]]+w[i]);
这样的顺序是因为我们现在可以忽略第i个物品的数量了,也就是说,只要当前的背包能够放得下,我就把它放进去。
。。。orz
网友评论