背包问题算法设计

1、背包问题算法设计题目描述：有n个物品，每个物品的重量为wi，取物品则效益增加pi，对于给定的一个能容纳重量为m的背包，怎样装包才能使获得的效益最大？每个物品的取值为xi，xi=0/1，0表示该物品不装包，1表示将该物品装入包中。以上描述就是一个经典的0/1背包问题。输入输出：输入一个n，然后输入w1,2,.,n,p1,2,.,n输出最大效益值和x1,2,.,n用0/1表示sampleinput3/n234/wi125/pisampleoutput6/最大效益值101/xi解题思路：假定决策次序为xn,xn-1,.,x1。在对xn做出决策之后，问题处于下列两种状态之一：背包的剩余容量为m，没有产

2、生任何效益；剩余容量是m-w，效益增长了p。显然，余下来的xn-1,xn-2,.,x1的决策相对于x所产生的问题状态应该是最优的，否则xn,xn-1,.,x1就不能是最优决策序列。设fjx是从物品1-j,背包容量为x的最优解则最优序列的解fnm对于任意的fix=maxfi-1x,fi-1x-wi+pi-（1）为了能向后递推而最后求出fnm,需要从f0x开始。对于所有x=0，有f0x=0，当x0时，有f0x=负无穷。根据（1）马上可解出0=x=w1的情况下f1x的值。接着又可以不断递推出f2,f3,.,fn在x相应的取值范围内的值。于是有求fnm的算法：for(i=1;i=n;i+)for(j=

3、1;j=0)fij=max(fi-1j,fi-1j-wi+pi);elsefij=fi-1j;一般而言，背包问题是要求一个最优值，如果要求输出这个最优值的方案，可以参照一般动态规划问题输出方案的方法：记录下每个状态的最优值是由状态转移方程的哪一项推出来的，换句话说，记录下它是由哪一个策略推出来的。便可根据这条策略找到上一个状态，从上一个状态接着向前推即可。设giv=0表示推出fiv的值时是采用了方程的前一项（也即fiv=fi-1v），giv表示采用了方程的后一项。注意这两项分别表示了两种策略：未选第i个物品及选了第i个物品。于是改写求fnm的过程为：for(i=1;i=n;i+)for(j=1

4、;j=0)fij=max(fi-1j,fi-1j-wi+pi);if(fij=fi-1j-wi+pi)gij=1;elsefij=fi-1j;那么求方案的向量的伪代码可以这样写i=n;j=m;while(i0)if(gij=0)xi=0;elsexi=1;j=j-wi;i-;最后输出向量x和fnm既可。算法空间分析：时间复杂度o(n*m)时间复杂度o(n*m)代码设计：#includeusingnamespacestd;#definen200#definemax(a,b)(ab?a:b)intmain()intn,m,i,j;intwn,pn,xn;intfnn,gnn;freopen(in.txt,r,stdin);while(cinnm)for(i=1;iwi;for(i=1;ipi;memset(f,0,sizeof(f);memset(g,0,sizeof(g);for(i=1;i=n;i+)for(j=1;j=0)fij=max(fi-1j,fi-1j-wi+pi);if(fij=fi-1j-wi+pi)gij=1;elsefij=fi-1j;i=n;j=m;while(i0)if(gij=0)x