9动态规划(02背包问题).doc

9动态规划(背包问题)9.2.4背包问题有n件物品，每件物品有一个重量和一个价值，同时有一个背包容量为wk，要求从n件物品中任取若干件，使重量之和=wk，而价值之和最大。五种不同类型背包1) 01背包 ，n件物品，每件物品要么不取，或者全取2) 可拆背包，每件物品可以拆开，任意选取3) 无限背包，每件物品有无穷多个4) 多重背包，每件物品有许多个，但是不是无穷。5) 关联背包，有些物品不能独立，必须和别的物品一道选取 01背包用子问题定义状态：即fiv表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：状态转移方程便是： fiv=maxfi-1v,fi-1v- wi+ ci例如 n=6 , wk=30 重量 w 5 13 7 10 8 14价值 C 16 28 18 20 17 31数组wi第i件物品的重量数组ci第i件物品的价值数组gij 表示前i件物品恰放入一个容量为j的背包可以获得的最大价值。012345678910111213141516171819202122232425262728293000000000000000000000000000000000100000161616161616161616161616161616161616161616161616161620000016161616161616162828282828444444444444444444444444443000001616181818181834343434343444444646464646626262626262400000161618181820203434343636384444464654545462626264646650000016161818182020343434363638444451515454546262626464716000001616181818202034343436363844475151545454626565656771递推关系 0 (i=0,0=j0,jw(i) max(gi-1j,gi-1j-wi+ci) (w(i)=j=wk)参考代码：#include #include #include using namespace std;#define MAXN 1010int cMAXN,wMAXN,gMAXNMAXN; int main()int n,wk,i,j;cinnwk;for(i=1;iwici;for(j=0;j=wk;j+)g0j=0;for(i=1;i=n;i+) for(j=0;jj) gij=gi-1j; else gij=max(gi-1j,gi-1j-wi+ci); coutgnwk;return 0;优化一：观察Gij可以发现，第i行只与i-1行进行比较，可以节约空间，防止数据量过大，不使用二维数组。#include #include #include using namespace std;#define MAXN 1010int cMAXN,wMAXN,g1MAXN; int main()int n,wk,i,j;cinnwk;for(i=1;iwici;for(j=0;j=wk;j+)g0j=0;for(i=1;i=n;i+) for(j=wi;j=wk;j+)g1j=max(g0j,g0j-wi+ci); for(j=0;j=wk;j+)g0j=g1j;coutg1wk;return 0;优化二：同样可以使用一维数组实现。参考代码：#include #include #include using namespace std;#define MAXN 1010int cMAXN,wMAXN,gMAXN; int main()int n,wk,i,j;cinnwk;for(i=1;iwici;for(i=1;i=wi;j-)/此处循环不能写成升序 gj=max(gj,gj-wi+ci);coutgwkendl;return 0;j按照wkwi逆循环，是因为要保证第i次循环中的状态gij是由状态gi-1j-wi递推而来。换句话说，正是为了保证每件物品只选一次，保证在选入第i件物品依据的是未选入该件物品的子结果gi-1j-wi。顺推结果：01234567891011121314151617181920212223242526272829000000000000000000000000000000010000016161616163232323232484848484864646464648080808080逆推结果：012345678910111213141516171819202122232425262728293000000000000000000000000000000000100000161616161616161616161616161616161616161616161616161601背包+路径记录+（价值最大/恰好装满）#include #include #include using namespace std;#define MAXN 1010#define INF 0x3F3F3F3F/作为无穷大的数，保证无穷大+无穷大=无穷大int cMAXN,wMAXN,gMAXN,numbMAXNMAXN; int main()int n,wk,i,j;cinnwk;/memset(g,-INF,sizeof(g);g0=0;/ 要求恰好装满背包memset(g,0,sizeof(g); / 只希望价值尽量大for(i=1;iwici;for(i=1;i=wi;j-)/此处循环不能写成升序 if(gjgj-wi+ci)gj=gj-wi+ci;for(int p=1;p=n;p+)numbjp=numbj-wip;numbji+=1;coutgwkendl;for(i=1;i=n;i+)if(numbwki)coutwi ;coutendl;/for(i=0;i=wk;i+)/打表numb、重量、价值/ for(j=1;j=n;j+)/ coutnumbij ;/ cout i giendl;/return 0; 可拆背包每件物品可以拆开，任意选取n=6 , wk=30重量 w 5 13 7 10 8 14价值 C 16 28 18 20 17 31基本思想：（贪心算法）按照c(i)/w(i)的值由大到小排序1618312817205714138103.22.522答案:16+18+31+28*2/ 无限背包(完全背包)，每件物品有无穷多个如果仍然按照解01背包时的思路，令fiv表示前i种物品恰放入一个容量为v的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程，像这样： fiv=maxfi-1v-k*wi+k*ci|0=k*wi=v例如 n=6 , wk=29 重量 w 5 13 7 10 8 14价值 C 16 28 18 20 17 31012345678910111213141516171819202122232425262728290000000000000000000000000000000100000161616161632323232324848484848646464646480808080802000001616161616323232323248484848486464646464808080808030000016161818183232343436484850505264646666688080828284400000161618181832323434364848505052646466666880808282845000001616181818323234343648485050526464666668808082828460000016161818183232343436484850505264646666688080828284 0 (i=0,0=j0,jw(i) max(gi-1j,gij-wi+ci) (w(i)=j=wk)参考代码一：#include #include #include using namespace std;#define MAXN 1010int cMAXN,wMAXN,g1MAXN; int main()int n,wk,i,j;cinnwk;for(i=1;iwici;for(j=0;j=wk;j+)g0j=0;for(i=1;i=n;i+) for(j=wi;j=wk;j+)g1j=max(g0j,g1j-wi+ci); for(j=0;j=wk;j+)g0j=g1j;coutg1wk;return 0;参考代码二：#include #include #include using namespace std;#define MAXN 1010#define INF 0x3F3F3F3F/作为无穷大的数，保证无穷大+无穷大=无穷大int cMAXN,wMAXN,gMAXN,numbMAXNMAXN; int main()int n,wk,i,j;cinnwk;/memset(g,-INF,sizeof(g);g0=0;/ 要求恰好装满背包memset(g,0,sizeof(g); / 只希望价值尽量大for(i=1;iwici;for(i=1;i=n;i+) for(j=wi;j=wk;j+)/此处循环不能写成反序 if(gjgj-wi+ci)gj=gj-wi+ci;for(int p=1;p=n;p+)numbjp=numbj-wip;numbji+=1;coutgwkendl;for(i=1;i=n;i+)if(numbwki)coutwi numbwkiendl;/for(i=0;i=wk;i+)/打表numb、重量、价值/ for(j=1;j=n;j+)/ coutnumbij ;/ cout i giendl;/return 0; 多重背包：每件物品有许多个 基本的方程只需将完全背包问题的方程略微一改即可，因为对于第i种物品有ni+1种策略：取0件，取1件取ni件。令fiv表示前i种物品恰放入一个容量为v的背包的最大权值，则有状态转移方程： fiv=maxfi-1v-k*wi+k*ci|0=k=ni w : 7 13 6 9 重量 C : 15 27 13 19 价值 D : 6 17 25 33 个数方法一：转化为01背包问题，取第i件物品有ni+1种策略（0ni），把第i件物品转化为ni件不同的物品。参考代码：#include #include #include using namespace std;#define MAXN 1010#define INF 0x3F3F3F3F/作为无穷大的数，保证无穷大+无穷大=无穷大int cMAXN,wMAXN,gMAXN,dMAXN,numbMAXNMAXN; int main()int n,wk,i,j,k;cinnwk;/memset(g,-INF,sizeof(g);g0=0;/ 要求恰好装满背包memset(g,0,sizeof(g); / 只希望价值尽量大for(i=1;iwicidi;for(i=1;i=n;i+) for(k=1;k=wi&k*wij;j-)/反序，同01背包 if (gjgj-wi+ci) gj=gj-wi+ci; for(int p=1;p=n;p+)numbjp=numbj-wip; numbji+=1; coutgwkendl;for(i=1;i=n;i+)if(numbwki)coutwi numbwkiendl;for(i=0;i=wk;i+)/打表numb、重量、价值 for(j=1;j=n;j+) coutnumbij ; cout i giendl;return 0;方法二：采取二进制分拆的方法，将ni件物品分为系数为1，2，42(k-1), ni-2k+1的物品，价值和重量分别乘这些系数。例如13拆分为1，2，4，6。再用方法二解决问题。复杂度为O(j*logni)参考代码：#include#include #include#define N 1000 /物品个数 #define M 100000 /所有物品可能的最大价值 #define INF 0x3F3F3F3F/作为无穷大的数，保证无穷大+无穷大=无穷大using namespace std;int mN,cN,wN,fM,numbMN;int V,n;void ZeroOnePack(int cost,int weight,int k,int i) /01背包 int v; for(v=V;v=cost;v-) if(fvfv-cost+weight)fv=fv-cost+weight;for(int p=1;p=n;p+)numbvp=numbv-costp;numbvi+=k;void CompletePack(int cost,int weight,int i)/完全背包 int v; for(v=cost;v=V;v+) if(fvfv-cost+weight)fv=fv-cost+weight;for(int p=1;p=V)/如果数量*价格大于总价转完全背包 CompletePack(cost,weight,i); return; k=1; /二进制法01背包 while(knV;/ 两种不同的初始化方式，根据情况自行选择 memset(f,0,sizeof(f); / 希望价格尽量大 /memset(f,-INF,sizeof(f);f0=0; / 要求恰好装满背包 for(i=1;iciwimi;/ci价钱wi价值mi个数！ for(i=1;i=n;i+) MultiplePack(ci,wi,mi,i); coutfVendl; for(i=1;i=n;i+)if(numbVi)coutci numbViendl; for(i=0;i=V;i+)/打表numb、重量、价值 for(int j=1;j=n;j+) coutnumbij ; cout i fiendl; return 0;二维费用的背包二维费用的背包问题是指对于每件物品，具有两种不同的费用，选择这件物品必须同时付出这两种代价，对于每种代价都有一个可付出的最大值（背包容量），求选择物品可以得到最大的价值。设第i件物品所需的两种代价分别为vi和ui，两种代价可付出的最大值（两种背包容量）分别为V和U，物品的价值为wi。分析：相比经典的01背包问题，二维费用背包问题增加了一维费用，于是我们需要在状态上增加一维。设sijk表示将前i件物品放入两种容量分别为j和k的背包时所能获得的最大价值，则状态转移方程为sijk=maxsi-1jk, si-1j-vik-ui+wi，递推边界为当i=0时sijk=0。和01背包类似，状态的维数可以轻易的从三维降低到二维，具体实现见代码。代码：for (int i=0; i=V; i+) for (int j=0; j=U; j+) sij=0; / 边界for (int i=1; i=vi; j-) for (int k=U; k=ui; k-) sjk=max(sjk, sj-vik-ui+wi); 分组背包有N件物品和一个容量为V的背包。第i件物品的费用是ci，价值是wi。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。算法这个问题变成了每组物品有若干种策略：是选择本组的某一件，还是一件都不选。也就是说设fkv表示前k组物品花费费用v能取得的最大权值，则有：fkv=maxfk-1v,fk-1v-ci+wi|物品i属于组k使用一维数组的伪代码如下：for 所有的组k for v=V.0 for 所有的i属于组k fv=maxfv,fv-ci+wi注意这里的三层循环的顺序，“for v=V.0”这一层循环必须在“for 所有的i属于组k”之外。这样才能保证每一组内的物品最多只有一个会被添加到背包中。例题：一个旅行者有最多能用V公斤的背包，现在有n件物品，他们的重量分别为w1,w2wn，他们的价值分别为c1,c2cn。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。输入格式：第一行，三个整数，V(背包容量，V=200)，n(物品数量，n=30),t(最大组号，t=10)；第二n+1行：每行三个整数wi,ci,p,表示每个物品的重量、价值、组号。输出格式：仅一行，一个数，表示最大总价值。输入样例：10 6 32 1 13 3 14 8 26 9 22 8 33 9 3输出样例：20参考代码：#include #include #include using namespace std;#define MAXN 1010int w50,c50,a4012,fMAXN;int max(int a,int b)return ab?a:b;int main()int V,n,t,i,j,k,p;cinVnt;/V背包容量，n物品数量，t小组数量memset(f,0,sizeof(f);memset(a,0,sizeof(a);for(i=1;iwicip;a0p+;/计算每个小组的数量aa0pp=i;/保存每个小组每个元素在物品中的序号for(i=1;i=0;j-)/枚举所有重量for(k=1;k=waki)/下标需要有效fj=max(fj,fj-waki+caki);coutfVendl;return 0;例题：一个学生用M天的时间复习N门课程，每门课程花费不同的天数，有不同的收获。问如何安排这M天，使得收获最大。输入：输入由多组数据组成。第一行包含两个正整数N和M，N是课程数，M是共有的天数。接下来是一个数组Aij，(1=i=N=100,1=j=M=100)。表示花费j天学习第i门课程的收获。输入到N=0和M=0结束。样例输入2 21 21 32 22 12 12 33 2 13 2 10 0样例输出346#include #include #include #include using namespace std;#define max(a,b) (ab?a:b)int N,M;int A101101;int f101;void GroupPack() memset(f,0,sizeof(f); int i,j,k; for(i=1;i=0;j-)/枚举不同容量 for(k=1;k=j;k+)/不同时间的课程 fj=max(fj,fj-k+Aik); / 为什么是fj-k？ coutfMNM) if(N=0&M=0) break; for(int i=1;i=N;i+) for(int j=1;jAij; GroupPack(); return 0;关联背包，有些物品不能独立，必须和别的物品一道选取 同0-1背包。例题：金明的预算方案noip2006day1 2 /20150418/20/金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子： 主 件 附 件 电脑 打印机，扫描仪 书柜 图书 书桌 台灯，文具 工作椅 无 如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有0个、1个或2个附件。附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数15表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是10元的整数倍）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。设第j件物品的价格为vj，重要度为wj，共选中了k件物品，编号依次为j1，j2，jk，则所求的总和为：vj1*wj1+vj2*wj2+ +vjk*wjk。（其中*为乘号）请你帮助金明设计一个满足要求的购物单。输入输入文件的第1行，为两个正整数，用一个空格隔开：N m 其中N（32000）表示总钱数，m（60）为希望购买物品的个数。）从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有3个非负整数v p q(其中v表示该物品的价格(v0，表示该物品为附件，q是所属主件的编号)输出输出文件只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值(200000)。样例输入1000 5800 2 0400 5 1300 5 1400 3 0500 2 0样例输出2200参考代码：#include #include #include using namespace std;#define MAXN 32100int N,m,w80,v80,a805,nMAXN,fMAXN;int max(int a,int b)return ab?a:b;int main() int i,j,k,p;cinNm;/N总金额m物品数k=0;for(i=1;iviwip;/v每件物品的价格w重要度p组别 wi=wi*vi;/题目要求价值为重要度*物品价格 if(p=0) a+k0=i;/k记录小组编号ak0为小组主件在物品序列中的编号 else np+;apnp=i;/np记录每个小组的附件编号，apnp为附件在物品序列中的编号for(i=1;i=