完全背包问题.ppt

完全背包问题完全背包问题（无限背包）（无限背包）主讲人：山成虎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背包问题的方程的确是很重要，可以推及其它类型的背包问题。背包问题的方程的确是很重要，可以推及其它类型的背包问题。核心代码：核心代码：fori=1.Nforv=0.Vfork=1.vdivwifiv=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背包中，我们使用一维数组来优化空间，完全背包中同样可以！背包中，我们使用一维数组来优化空间，完全背包中同样可以！这个算法使用一维数组，核心代码如下：这个算法使用一维数组，核心代码如下：fori=1.Nforv=0.Vfv=maxfv,fv-wi+ci;【问题描述问题描述】设有设有n种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为的，同时有一个背包，最大载重量为M，今从，今从n种物品中选取若干件种物品中选取若干件(同一种物品同一种物品可以多次选取可以多次选取)，使其重量的和小于等于，使其重量的和小于等于M，而价值的和为最大。，而价值的和为最大。【输入格式输入格式】第一行：两个整数，第一行：两个整数，M(背包容量，背包容量，M=200)和和N(物品数量，物品数量，N=30)；第第2.N+1行：每行二个整数行：每行二个整数Wi,Ci，表示每个物品的重量和价值。，表示每个物品的重量和价值。【输出格式输出格式】仅一行，一个数，表示最大总价值。仅一行，一个数，表示最大总价值。【样例输入样例输入】knapsack.in10421334579【样例输出样例输出】knapsack.outmax=12【解法一：二维数组解法一：二维数组】【算法分析算法分析】设设f(i，x)表示前表示前i件物品，总重量不超过件物品，总重量不超过x的最优价值，则的最优价值，则f(i，x)=max(f(i，x-wi)+ci,f(i-1，x)；f（n，m）即为最优解。）即为最优解。【参考程序参考程序】:（顺推法）（顺推法）Programknapsack;Constmaxm=200;maxn=30;vari,x,n,m:integer;w,c:array1.maxnofinteger;f:array0.maxn,0.maxmofinteger;BEGINfillchar(w,sizeof(w),0);fillchar(c,sizeof(c),0);readln(m,n);/背包容量背包容量m和物品数量和物品数量nfori:=1tondo/每个物品的重量和价值每个物品的重量和价值read(wi,ci);fori:=1tondo/f(i，x)表示前表示前i件物品，总重量不超过件物品，总重量不超过x的最优价值的最优价值forx:=1tomdoifxfi,x-wi+cithenfi,x:=fi-1,xelsefi,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=witheniffx-wi+cifxthenfx:=fx-wi+ci;writeln(max=,fm);/f(m)为最优解为最优解END.【参考程序参考程序2】:（顺推法）（顺推法）programknapsack04;constmaxm=200;maxn=30;typear=array0.maxnofinteger;varm,n,x,i,t:integer;c,w:ar;f:array0.maxmofinteger;BEGINreadln(m,n);/背包容量背包容量m和物品数量和物品数量nfori:=1tondoreadln(wi,ci);/每个物品的重量和价值每个物品的重量和价值f0:=0;fori:=1tondoforx:=1tomdo/设设f(x)表示重量不超过表示重量不超过x公斤的最大价值公斤的最大价值ifx=witheniffx-wi+cifxthenfx:=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;后面两个方程是一个意思。希望你能够对这三个状态转后面两个方程是一个意思。希望你能够对这三个状态转移方程都仔细地体会，不仅记住，也要弄明白它们是怎么得移方程都仔细地体会，不仅记住，也要弄明白它们是怎么得出来的，最好能够自己想一种得到这些方程的过程。出来的，最好能够自己想一种得到这些方程的过程。