浅谈贪心与动归

浅谈贪心与动归初学时想必都会对两者的认识有一些混淆概念性质的就不赘述了来谈谈我在刷题过程中对两者的见解(诚心接受各位的指正)从搜索到贪心——求解算法的优化这篇文章非常值得一看P1478陶陶摘苹果(升级版)对应的oj题目对比贪心像是动归的一个特例动归的核心在于:状态转移,找出那个转移方程贪心的核心在于:局部选取最优解,并且选取的贪心策略不会影响到其他的状态用01背包举个例子在n件物品取出若干件放在空...

浅谈贪心与动归

初学时 想必都会对两者的认识有一些混淆
概念性质的就不赘述了
来谈谈我在刷题过程中对两者的见解(诚心接受各位的指正)
从搜索到贪心——求解算法的优化 这篇文章非常值得一看
P1478 陶陶摘苹果(升级版) 对应的oj题目

对比

贪心像是动归的一个特例
动归的核心在于:状态转移,找出那个转移方程
贪心的核心在于:局部选取最优解,并且选取的贪心策略不会影响到其他的状态

用01背包举个例子

在n件物品取出若干件放在空间为c的背包里,每件物品的体积为w1 w2...wn,与之相对应的价值为v1 v2...vn,最终使背包所装物品的总价值最高
代码如下,基本上大家都会写

int dp[i][j]; //dp[i][j] 表示取到第i个物品,背包容量为jint 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 10000for(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.guoxiongfei.cn/cntech/18448.html
0