【模板】各种背包问题&讲解
2018-06-17 21:07:09来源:未知 阅读 ()
背包问题集合
一般来说,动态规划(DP)都是初学者最难闯过的一关,而在这里详细解说动态规划的一种经典题型:背包问题。
这里介绍的背包分为以下几种:01背包,完全背包,多重背包,混合背包,二维费用的背包。(以后会持续更新)
【一:01背包】
首先放上例题:
01背包问题
【题目描述】:
一个旅行者有一个最多能装M公斤的背包,现在有n件物品,他们的重量分别是W1,W2…Wn,它们的价值分别是C1,C2……Cn,求旅行者能够获得的最大总价值。
【输入格式】:
第一行:两个整数,M,(背包容量,M<=200)和N(物品数量N<=30)
第2至N+1行,每行两个整数,Wi,Ci,表示每个物品的重量和价值。
【输出格式】:仅一行,一个数,表示最大总价值。
【输入样例#1】:
10 4
2 1
3 3
4 5
7 9
【输出样例#1】:12
【输入样例#2】:
8 4
5 6
4 2
1 2
01背包问题可以说是最简单的背包问题,简单之处就在:他的每一个物品都只有一个。
首先定义一个f[MAXN][MAXN]数组,用来记录最大价值。即:f[i][v]表示的就是当前i件物品放入一个容量为v的背包的时候可以获得的最大价值。
01背包的状态转移方程式便是:f[i][v]=max(f[i-1][v],f[i-1][v-w[i]]+c[i])。
众所周知DP问题最重要的便是状态转移方程式了,那么这个状态转移方程式究竟是怎么来的呢??
详解来啦“!!!
既然说了是“将第i件物品放入背包”,那么如果只考虑第i件物品的方式策略,那么就只和第i-1件物品有关了,如果是放第i件物品,那么问题就转化为:“前i-1件物品放入容量为v的背包中”,此时能够获得的最大价值就是f[i-1][v-w[i]],也就是第i-1件物品放入容量为v(原来的总容量)减去w[i](第i件物品的占容)产生的最优价值,再加上放通过入第i件物品增加的价值c[i]。
那么放入第i件物品产生的最大价值就是要在”放“,或者是”不放“中选择了,”不放“的话,产生的价值就是f[i-1][v],”放“的话,产生的最大价值就是,f[i-1][v-w[i]]+c[i])。那么我们应该怎么选择呢,很简单,取最大的,就是产生的最大价值啦。
若物品数量为n,背包总容量为m,那么循环到最后,答案也就是f[n][m]啦。
那么附上代码:::
#include<bits/stdc++.h>
#define MAXN 0x7ff
using namespace std;
int m,n,w[MAXN],c[MAXN];
int f[MAXN][MAXN],i,j;//f[i][v]表示第i件物品放入容量为v的背包所能产生的最大价值。
int maxn(int x,int y)//比较,输出最大值
{
if(x>y)
return x;
else
return y;
}
int main()
{
cin>>m>>n;
for(i=1;i<=n;i++)
cin>>w[i]>>c[i];//输入不解释
for(i=1;i<=n;i++)
for(j=m;j>0;j--)
{
if(w[i]<=j)
f[i][j]=maxn(f[i-1][j],f[i-1][j-w[i]]+c[i]);//状态转移方程式。
else f[i][j]=f[i-1][j];
}
cout<<f[n][m];
return 0;
}
好了以上就是最简单的01背包模板了qwq。
【二:完全背包问题】
还是例题打头阵。
完全背包问题
【题目描述】
设有n种物品,每种物品有一个价值,但每种物品的数量是无限的,同时有一个背包,最大承载量微m,今从n种物品中选取若干件,(同一种物品可以多次选举)使其重量的和小于等于m,而且价值的和最大。
【输入】共N+1行
第一行:两个整数:M(背包容量M<=200)和N(物品数量,N<=30);
第二行至第N+1行,每行两个整数,Wi,Ci,表示每个物品的重量和价值。
【输出】
近一行:一个数,表示最大的价值;
【输入样例】
10 4
2 1
3 3
4 5
7 9
【输出样例】
12
有的小伙伴们可能一看到例题就会发现一个与01背包不同的地方:每种物品的数量是无限多的。没错,这就是完全背包问题。其实这个问题没有比01背包难多少,只是不是很好想。
既然每种物品所取的数量可能是1,2,3.......,所以与它相关的策略便不是取或者不取的问题了,而是,取不取,取多少的问题了。既然同样是背包问题,那么我们可不可以考虑延续01背包的方法来做呢,答案是Yes。其实与01背包不同的地方就是只有放进去的每种物品的件数不一定是1就是了,那么只要多一重关于每种物品取多少的循环不就可以了吗。相对的,其状态转移方程式也要略有改动,变为:f[i][v]=max(f[i-1][v-k*w[i]]+k*c[i],f[i-1][v]),可见就是比01背包多了一个k而已,而这个k就是循环的这第i种物品取的件数。
现在解释一下原因:首先我们想一下为甚么在上题中的01背包代码中第二重循环是for(int j=m;j>=0;j--)而不是for(int j=1;j<+m;j++)呢??(你就没有怀疑过吗??~~~)
Because~因为:要保证第i次循环里的状态f[i][v]是由状态f[i][[v-w[i]]递推而来的,也就是为了保证每件物品只选一次,保证在考虑“选入第i件物品”这件策略时,依据的是一个绝不可能选入第i种物品的子结果f[i][v-w[i]]。如果如果还不是很明白,大家可以画一个表格来自己推一下,看看逆序和正序时得到的结果有什么不同。。。。。。
好了重点来了!! : 现在大家已经知道了01背包的顺序,那么现在问题来了:完全背包的顺序呢??
考虑“加选一件第i种物品”这种策略时,却正需要一个可能已经选入第i种物品的子结果f[i][v=w[i]],所以就可以并且必须采用v=0,.....v的顺序循环,这就是则个简单的程序何以成立的原因啦。
然后给大家附上代码:: //不准抄袭!! 好吧像我这种蒟蒻代码有谁会抄呢 呵呵~~
#include<iostream> #include<cstdio> using namespace std; const int MAXN=31,MAXM=201; int m,n,w[MAXN],c[MAXN],f[MAXN][MAXM]; int main() { scanf("%d%d",&m,&n); for(int i=1;i<=n;i++) scanf("%d%d",&w[i],&c[i]); for(int i=1;i<=n;i++) for(int v=1;v<=m;v++) if(v<w[i]) f[i][v]=f[i-1][v]; else {if(f[i-1][v]>f[i][v-w[i]]+c[i]) f[i][v]=f[i-1][v]; else f[i][v]=f[i][v-w[i]]+c[i];} printf("%d",f[n][m]); return 0; }//这个码风不是很好看,大家看不惯可以改一改......
【三:多重背包问题】
好了依然是看例题::
模板例题:庆功会
【题目描述】
设有n种物品,每种物品有一个价值,但每种物品的数量是有限的,同时有一个背包,最大承载量微m,今从n种物品中选取若干件,(同一种物品可以多次选举)使其重量的和小于等于m,而且价值的和最大。
【输入】共N+1行
第一行:两个整数:N(物品数量,N<=30)和M(背包容量M<=200)
第二行至第N+1行,每行两个整数,Wi,Ci,Si,分别表示每个物品的重量、价值、数量。
【输出】
近一行:一个数,表示最大的价值;
【输入样例】
5 1000
80 20 4
40 50 9
30 50 7
40 30 6
20 20 1
【输出样例】
1040
这个题目就又不一样了,因为题目中说的每一件物品的件数是“有限的”,也就是说可以是1、2......但也不是无限。
这个看起来可能就比较e xin,但是如果仔细想一想,其实也并不是很难。
(蒟蒻认为的)重点详解:
做法1:和完全背包接轨:完全背包里面有一个k,用来表示物品的个数,这里面也是一样的,因为对于第i种物品,我们可以设置他有n[i]+1种取数策略,:取0、1.....n[i]件,so我们再次设置一个f[i][v]表示前i种物品放入一个容量为v的背包所能产生的最大价值,那么:f[i][v]=max(f[i-1)[v-k*w[i]]+k*c[i],f[i-1][v]),那么复杂度就是O(V*Σn[i])。
显然,上方做法时间复杂度太高。于是就有了第二个方法。
做法2:和01背包接轨。大家可能都觉得完全背包比01背包更要高大上一些,但是很不幸,做法2是要远远优于做法1的。先给大家一个引路思想,第i件物品有n[i]的数量,那么是不是可以把它转化为n个数量只有一个的物品呢??看到这里,你恍然大悟:哦,好巧妙。
而事实上,如果你只想到这里,就开始兴奋无脑地开始打代码的话,你就会呵呵进化成神犇了。。。。。你您可以算一算如果这样做的话时间复杂度是多少:O(V*Σn[i]) ............
好极了,可是我并没有在逗你啊。。。。。
那么接下来就是优化了,在这里,我们考虑二进制优化。
方法:将第i件物品分成若干件物品,每个物品有一个系数l,这件物品的费用和价值军事原来的费用和价值乘以l,使这些系数分别为1,2,4...2(k-1)余出来的再拿出来就是n[i]-2(k+1),且k是满足n[i]-2(k+1)>0的最大整数。(例:13分为1,2,4,6)。
这样就将第i件物品分成了O(logn[i)种物品,将时间复杂度降低成为了O(V*Σlogn[i])的01背包问题,改进是不是很大呢?
下面是代码:
#include<iostream>
#include<cstdio>
#define MAXN 10001
#define MAXM 6001
using namespace std;
int v[MAXN],w[MAXN],f[MAXM];
int n,m,n1;
int max(int a,int b)
{
if(a>b) return a;
else return b;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
int x,y,s,t=1;
scanf("%d%d%d",&x,&y,&s);
while(s>=t)
{
v[++n1]=x*t;
w[n1]=y*t;
s-=t;
t*=2;
}
v[++n1]=x*s;
w[n1]=y*s;
}
for(int i=1;i<=n1;i++)
for(int j=m;j>=v[i];j--)
f[j]=max(f[j],f[j-v[i]]+w[i]);
printf("%d\n",f[m]); return 0;
}
【四:混合三种背包问题】
大概很多人一看到这个就泪奔了,对,没错,就是把01、完全、多重背包混合起来考你。你可能肯定觉得很恶心,觉得难极了,确实,对于没有学过前几种背包的人来说,这是一个很大的挑战,但是不要忘了,我们已经学完了呀!所以,我哦们就可以很轻易地将这一个难题转化为极个简单的子题了!!
其实也不用怎么解释了,先判断该物品是不是属于完全背包,if(YES)->用完全背包去做,if(NOT)->用混合背包去做(因为01背包本身即是多重背包的一个样例,用多重背包做完全没有问题的。)
好了下面附上代码:
#include<iostream>
#include<cstdio>
using namespace std;
int m,n,w[31],c[31],p[31],f[201];
int max(int a,int b)
{
if(a>b) return a;
else return b;
}
int main()
{
scanf("%d%d",&m,&n);
for(int i=1;i<=n;i++)
scanf("%d%d%d",&w[i],&c[i],&p[i]);
for(int i=1;i<=n;i++)
if(p[i]==0)
{
for(int j=w[i];j<=m;j++)
f[j]=max(f[j],f[j-w[i]]+c[i]);
}
else
{
for(int j=1;j<p[i];j++)
for(int k=m;k>=w[i];k--)
f[k]=max(f[k],f[k-w[i]]+c[i]);
}
printf("%d",f[m]);
return 0;
}
【五:二维费用的背包】
这又是一种新的背包问题了,显而易见,他的费用是二维的。什么叫二维的呢?先来看一道例题,你就能明白了。
例题:潜水员
【问题描述】
潜水员为了潜水要使用特殊的装备,他有一个带2种气体的气缸,一个为氧气,一个为氮气,让钱会员下潜的深度需要各种数量的氧和氮,潜水员有一定数量的气缸,每个气缸都有重量和气体容量,潜水员为了完成她的工作需要特定的数量的氧和氮,他完成工作需要气缸的总重的最低限度是多少??
【输入格式】
第一行:两个整数,m,n,(1<=m<=21,1<=n<=79)。他们表示氧,氮各自需要的量。
第二行:为整数k(1<=k<=1000)表示气缸的个数。
此后的k行每行包括一个ai,bi,ci,(1<=ai<=21,1<=bi<=79,c<=ci<=800)三个整数,分别表示第i个气缸里的氧的容量,氮的容量,以及气缸重量。
【输出格式】
仅一行,包含一个整数,为重量和的最低值。
【输入样例】
5 60
5
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119
【输出样例】
249
好的,我觉得大多数人可能都已经明白了什么叫二维了,在这个例题中,每一个气缸油两种不同的费用,选择这件物品必须同时付出这两种代价,对于每一种代价有一个背包容量,问怎么样选择物品可以得到最大的价值。
接下来不只针对例题,而是对于大多数二维背包题:
我们可以定义第i种物品的代价分别为a[i]和b[i],两种背包容量分别为V和U,第i件物品的价值为c[i]。
那么显而易见,我们的算法需要增加一维,那么就将我们的f再增加一维即可,那么就有了状态转移方程式::
f[i][v][u]=max)f[i-1][v][u],f[i-1][v-a[i]][u-b[i]]+c[i]),当然,当物品只取一次是的时候变量v和u采取逆序循环。
但有的时候,很多良心的题经常是将二维背包以一种有一点隐晦的方式表示出来,例如:最多只能取M件物品,此时就又多了一个“件数”的费用,设f[v][m]表示付出费用v,最多选m件的时候可以得到的最大收入。之后便可以针对01、完全、多重背包采用不同的方式进行运算了。最后,在f[0 -> V][1 -> M]范围内寻找答案。
然后,附上【潜水员】例题的代码。
#include<iostream> #include<cstdio> #include<cstring> #define MAXN 1001 #define MAXM 101 using namespace std; int v,u,k; int a[MAXN],b[MAXN],c[MAXN]; int f[MAXM][MAXM]; int main() { memset(f,127,sizeof(f)); f[0][0]=0; scanf("%d%d%d",&v,&u,&k); for(int i=1;i<=k;i++) scanf("%d%d%d",&a[i],&b[i],&c[i]); for(int i=1;i<=k;i++) for(int j=v;j>=0;j--) for(int l=u;l>=0;l--) { int t1=j+a[i],t2=l+b[i];; if(t1>v) t1=v; if(t2>u) t2=u; if(f[t1][t2]>f[j][l]+c[i]) f[t1][t2]=f[j][l]+c[i]; } printf("%d",f[v][u]); return 0; }
好了,关于背包问题就先说到这里(持续更新。。。),如果有不明白个或者错误的地方可以给我留言。。。
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 关于各种不同开发语言之间数据加密方法(DES,RSA等)的互通的 2020-06-07
- C++冒泡排序 (基于函数模板实现) 2020-05-31
- C++ 模板类vector 2020-05-31
- C++ 模板类array 2020-05-31
- C++ 模板类vector 2020-05-30
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash