完全背包问题

1、完全背包问题（无限背包）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

2、|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件物品”这件策略时，

3、依据的是一个绝无已经选入第i件物品的子结果fi-1v-wi。而现在完全背包的特点恰是每种物品可选无限件，所以在考虑“加选一件第i种物品”这种策略时，却正需要一个可能已选入第i种物品的子结果fiv-wi，所以就可以并且必须采用v= 0.V的顺序循环。这就是这个简单的程序为何成立的道理。 这个算法也可以以另外的思路得出。例如，基本思路中的状态转移方程可以等价地变形成这种形式：fiv=maxfi-1v,fiv-wi+ci，将这个方程用一维数组实现，便得到了上面的核心代码。3 空间优化01背包中，我们使用一维数组来优化空间，完全背包中同样可以！这个算法使用一维数组，核心代码如下： for i=1.N

4、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.in10 42 13 34 57 9【样例输出】knapsack.outmax=12【解法一：二维数

5、组】【算法分析】设 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;BEGINfillchar(w,sizeof(w),0); fillchar(c,sizeof(c),0); readln(m,n); /背包容量m和物品数量n f

6、or 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:=fi,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+cif

7、x 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;BEGINreadln(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*