初学时 想必都会对两者的认识有一些混淆
概念性质的就不赘述了
来谈谈我在刷题过程中对两者的见解(诚心接受各位的指正)
从搜索到贪心 -- 求解算法的优化 这篇文章非常值得一看
P1478 陶陶摘苹果(升级版) https://www.luogu.org/problemnew/show/P1478 对应的 oj 题目
对比
贪心像是动归的一个特例
动归的核心在于: 状态转移, 找出那个转移方程
贪心的核心在于: 局部选取最优解, 并且选取的贪心策略不会影响到其他的状态
用 01 背包举个例子
在 n 件物品取出若干件放在空间为 c 的背包里, 每件物品的体积为 w1 w2...wn, 与之相对应的价值为 v1 v2...vn, 最终使背包所装物品的总价值最高
代码如下, 基本上大家都会写
- int dp[i][j]; //dp[i][j] 表示取到第 i 个物品, 背包容量为 j
- int pack01(int v[],int w[],int n,int c){ //value weight number capacity
- for(int i=1;i<=n;++i)
- for(int j=1;j<=c;++j){
- if(w[i]>j) dp[i][j]=dp[i-1][j];
- else dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
- }
- }
空间优化 一维
- for(int i=1;i<=n;i++)
- for(int j=c;j>=1;j--){ // 注意从后往前
- if(w[i]<=j){ // 二维变一维
- dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
- }
- }
更简洁
- for(int i=1;i<=n;i++)
- for(int j=c;j>=w[i];j--){
- dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
- }
但如果将 v1 v2...vn 这些每个物品对应的价值都变成 1(v1=v2=...=vn=1)
这样一来, 每个物品的价值都相同. 无论你有多重, 你的价值和别人都一样
很显然, 我们只要把物品的重量进行排序, 先拿轻的再拿重的, 结果必然最优
动归加上一个特例 就这样成为了贪心可解决的题目
并且时间复杂度 O(n)直接下降到排序的 nlogn
再来举个更接地气的栗子
找纸币
基本上每个国家设计的货币都是符合贪心原则的
我国的纸币面额分别为: 100 元, 50 元, 20 元, 10 元, 5 元, 2 元, 1 元
当需要找钱给别人时, 先找大面值的纸币再找小面值的, 最后一定是纸币数量最少的
但如果面额是 1 元, 5 元, 11 元的纸币
当你找别人 15 元时, 按照贪心规则, 找的是一张 11 元和 4 张 1 元的, 一共 5 张
而正确答案显而易见是 3 张 5 元的, 一共 3 张
这就不符合贪心策略了, 这时怎么来找到最少的? 这就需要用到动归了
这其实是完全背包 (每件物品可以取多次) 的模板
必须把背包装满, 即正好找出零钱, 不多也不少(会影响初始化, 文末见背包九讲)
每个物品价值 v[i]=1, 并且不是总价值最大, 而是纸币数量最小 max->min
- int m[4]={0,1,5,11};
- int dp[5][20]; //dp[i][j] i 表示纸币种类, j 表示找回的零钱
- // 转移方程 dp[i][j]=min(dp[i-1][j],dp[i][j-m[i]]+1);
- #define inf 10000 // 若背包则是 -∞
- // 初始化
- for(int i=0;i<=3;++i)
- for(int j=0;j<=15;++j){
- if(j==0) dp[i][j]=0;
- else dp[i][j]=inf;
- }
- for(int i=1;i<=3;++i){
- for(int j=0;j<=15;++j){
- if(j>=m[i]) dp[i][j]=min(dp[i-1][j],dp[i][j-m[i]]+1);
- else dp[i][j]=dp[i-1][j];
- // 请注意转移方程中 dp[i][j-m[i]]+1 里的[i]
- // 而 01 背包是[i-1], 这是物品能否取多次的关键所在
- }
- }
- cout<<dp[3][15];
空间优化
- int m[4]={0,1,5,11};
- int dp[20];
- #define inf 10000
- for(int j=0;j<=15;++j){
- if(j==0) dp[j]=0;
- else dp[j]=inf;
- }
- for(int i=1;i<=3;++i){
- for(int j=m[i];j<=15;++j){
- dp[j]=min(dp[j],dp[j-m[i]]+1);
- }
- }
- cout<<dp[15];
如果是第一种问法, 要求恰好装满背包, 那么在初始化时除了 F[0] 为 0 , 其它
F[1..V ] 均设为 −∞ , 这样就可以保证最终得到的 F[V ] 是一种恰好装满背包的最优解.
如果并没有要求必须把背包装满, 而是只希望价格尽量大, 初始化时应该将 F[0..V ]
全部设为 0 .
这是为什么呢? 可以这样理解: 初始化的 F 数组事实上就是在没有任何物品可以放
入背包时的合法状态. 如果要求背包恰好装满, 那么此时只有容量为 0 的背包可以在什
么也不装且价值为 0 的情况下被 "恰好装满", 其它容量的背包均没有合法的解, 属于
未定义的状态, 应该被赋值为 -∞ 了. 如果背包并非必须被装满, 那么任何容量的背包
都有一个合法解 "什么都不装", 这个解的价值为 0 , 所以初始时状态的值也就全部为 0
了.
取自《背包问题九讲》1.4 初始化的细节问题
来源: https://www.cnblogs.com/lidasu/p/10957495.html