完全背包问题

单击此处编辑母版标题样式,单击此处编辑母版副标题样式,完全背包问题,（无限背包）,1,问题,2,基本思路,3,空间优化,4,小结,1,问题,有,N,种物品和一个容量为,V,的背包，每种物品都有无限件可用。第,i,种物品的费用是,wi,，价值是,ci,。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。,2,基本思路,这个问题非常类似于,01,背包问题，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取,0,件、取,1,件、取,2,件,等很多种。如果仍然按照解,01,背包时的思路，令,fiv,表示前,i,种物品恰放入一个容量为,v,的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程：,fiv=maxfi-1v-k*wi+k*ci|0=k*wi= v,。,将,01,背包问题的基本思路加以改进，得到了这样一个清晰的方法。这说明,01,背包问题的方程的确是很重要，可以推及其它类型的背包问题。,核心代码：,for i=1.N,for v=0.V,for k=1.v div wi,fiv=maxfi-1v,fi-1v-k*wi+k*ci;,你会发现，这个伪代码与,01,背包问题的伪代码只有,v,的循环次序不同而已。为什么这样一改就可行呢？首先想想为什么,01,背包问题中要按照,v=V.0,的逆序来循环。这是因为要保证第,i,次循环中的状态,fiv,是由状态,fi-1v-wi,递推而来。换句话说，这正是为了保证每件物品只选一次，保证在考虑“选入第,i,件物品”这件策略时，依据的是一个绝无已经选入第,i,件物品的子结果,fi-1v-wi,。而现在完全背包的特点恰是每种物品可选无限件，所以在考虑“加选一件第,i,种物品”这种策略时，却正需要一个可能已选入第,i,种物品的子结果,fiv-wi,，所以就可以并且必须采用,v= 0.V,的顺序循环。这就是这个简单的程序为何成立的道理。,这个算法也可以以另外的思路得出。例如，基本思路中的状态转移方程可以等价地变形成这种形式：,fiv=maxfi-1v,fiv-wi+ci,，将这个方程用一维数组实现，便得到了上面的核心代码。,3,空间优化,01,背包中，我们使用一维数组来优化空间，完全背包中同样可以！,这个算法使用一维数组，核心代码如下：,for i=1.N,for v=0.V,fv=maxfv,fv-wi+ci;,【,问题描述,】,设有,n,种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为,M,，今从,n,种物品中选取若干件,(,同一种物品可以多次选取,),，使其重量的和小于等于,M,，而价值的和为最大。,【,输入格式,】,第一行：两个整数，,M(,背包容量，,M=200),和,N(,物品数量，,N=30),；,第,2.N+1,行：每行二个整数,Wi,Ci,，表示每个物品的重量和价值。,【,输出格式,】,仅一行，一个数，表示最大总价值。,【,样例输入,】knapsack.in,10 4,2 1,3 3,4 5,7 9,【,样例输出,】knapsack.out,max=12,【,解法一：二维数组,】,【,算法分析,】,设,f(i,，,x),表示前,i,件物品，总重量不超过,x,的最优价值，则,f(i,，,x)=max(f(i,，,x-wi)+ci,f(i-1,，,x),；,f,（,n,，,m,）即为最优解。,【,参考程序,】:,（顺推法）,Program knapsack;,Const maxm=200;maxn=30;,var i,x,n,m:integer;,w,c:array1.maxn of integer;,f:array0.maxn,0.maxm of integer;,BEGIN,fillchar(w,sizeof(w),0); fillchar(c,sizeof(c),0);,readln(m,n); /,背包容量,m,和物品数量,n,for i:=1 to n do /,每个物品的重量和价值,read(wi,ci);,for i:=1 to n do /f(i,，,x),表示前,i,件物品，总重量不超过,x,的最优价值,for x:=1 to m do,if xfi,x-wi+ci then fi,x:=fi-1,x,else fi,x:=f,i,x-wi+ci;,writeln(max=, fn,m); / f(n,，,m),为最优解,END.,【,解法一：一维数组,】,【,算法分析,】,本问题的数学模型如下：,设,f(x),表示重量不超过,x,公斤的最大价值， 则,f(x)=maxf(x-wi)+ci,当,x=wi,，,1=i=wi then if fx-wi+cifx then fx:= fx-wi+ci ;,writeln(max=,fm); / f(m),为最优解,END.,【,参考程序,2】:,（顺推法）,program knapsack04;,const maxm=200;maxn=30;,type ar=array0.maxn of integer;,var m,n,x,i,t:integer;,c,w:ar;,f:array0.maxm of integer;,BEGIN,readln(m,n); /,背包容量,m,和物品数量,n,for i:= 1 to n do,readln(wi,ci); /,每个物品的重量和价值,f0:=0;,for i:=1 to n do,for x:=,1 to m,do /,设,f(x),表示重量不超过,x,公斤的最大价值,if x=wi then if fx-wi+cifx then fx:= fx-wi+ci ;,writeln(max=,fm); / f(m),为最优解,END.,上面的代码中两层,for,循环的次序可以颠倒,4,小结,完全背包问题也是一个相当基础的背包问题，它有两个状态转移方程：,fiv=maxfi-1v-k*wi+k*ci|0=k*wi= v,；,fiv=maxfi-1v,fiv-wi+ci,；,fv=maxfv,fv-wi+ci;,后面两个方程是一个意思。希望你能够对这三个状态转移方程都仔细地体会，不仅记住，也要弄明白它们是怎么得出来的，最好能够自己想一种得到这些方程的过程。,