动态规划(二):背包动态规划基础

Source
版权声明:转载请注明出处(作者转载的文章除外) https://blog.csdn.net/guoyangfan_/article/details/81154655

继续上文--线形动态规划

(二).背包动态规划:

觉得背包动态规划比线形动态规划简单多了。。

1. 种类

   背包动态规划的种类有很多,如:01背包,完全背包,多重背包,混合背包,二维背包,分组背包。。。

2.作法

   在这里就不全讲了(懒癌发作qwq),只讲一下我自己的见解吧。

  先放01背包题目:

  01背包模板题--luogu

   

#include<bits/stdc++.h>
using namespace std;
#define N 10000
int n,m,i,j;
int w[N],c[N],f[N];
int main()
{
	scanf("%d%d",&m,&n);
	for(i=1;i<=n;++i)
	scanf("%d%d",&w[i],&c[i]);
	for(i=1;i<=n;++i)
	for(j=m;j>=w[i];--j)
	f[j]=max(f[j],f[j-w[i]]+c[i]);
	printf("%d",f[m]);
}

 

没错,很短!

我们设n表示有n件物品,用i枚举每件物品;设m表示有m个空间容量,用j来枚举有j个容量时最多能装下的价值。

那么好了,方程就是:

for(i=1;i<=n;++i)
  for(j=m;j>=w[i];--j)
  f[j]=max(f[j],f[j-w[i]]+c[i]);

emmm。。我相信大家都看懂了。max()里第一个和线形动态规划差不多,表示不选,则空间容量并不减少。第二个表示当空间剩下j时用w[i]的体积的物体,获得价值为c[i],那么我们就调用空间为f[j-w[i]]的数;(若f[j-w[i]]已经有决策了,那么f[j]得到的值一定更加逼近最优解);

 

emmm。。。再放一个完全背包的作法吧

题面:

完全背包模板---lougu

#include<bits/stdc++.h>
using namespace std;
#define maxn 100001
int f[maxn],i,j,k,w[maxn],n,m,v,c[maxn];
int main()
{
	cin>>v>>n;
	for(i=1;i<=n;++i)
	scanf("%d%d",&w[i],&c[i]);
	for(i=1;i<=n;++i)
	for(j=w[i];j<=v;++j)
	f[j]=max(f[j],f[j-w[i]]+c[i]);
	printf("%d",f[v]);
}

  好吧好吧,完全背包其实和01背包差不多,但要记住一点:完全背包第二层枚举的循环是从w[i]开始的!不是从总空间量来开始枚举的!因为从w[i]枚举有可能一个物品选多次,而从总空间量开始枚举是无法办到的因为j是不断递减的,那么j-w[i]是永远不可能相等的(在同一个物品的情况下),如果递增的话,j-w[i] 有可能重叠,这样会计算到同种物品用多次这一情况);

 

多重背包。。。

其实就是01背包的变形。方法1:在枚举物品序号的循环下面加一重循环循环次数为物品的数量。方法2:二进制分解,将物品个数打包,第一个包重量 1个*w,价值c,第二个 2个*w,价值2*c,第三个 4个*w,价值4*c,第四个 8个*w,价值8*c。。(当然在限度内)。如有剩下把剩下的物品单独打一个包。(为什么呢?有没有发现,1,2,4,8。。。(还有剩余的物品的个数)这些数能组成总的个数范围以内所有的正整数

 

混合背包。。。

将两种背包结合起来(多重背包和完全背包)。若当前物品供应量是无限的,用完全背包方程,不然用01背包方程的改进版(01背包上套一个循环次数为当前物品的数量)

 

二维背包。。。

在枚举时用3重循环,第二层表示最大容量1号,第三层表示最大容量2号,然后用法就和 01背包或者完全背包 差不多了。

 

好了好了,点到为止,我们的目标是理解动态规划是如何运行的,当我们理解后,其他不会的算法也就会了。

重要的事再说一遍:我们要把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解。

下一期,区间动态规划。