文档介绍：计算机算法(2)汪洋dawang198607@主要内容背包问题搜索树递归0-1背包问题给定n种物品和一背包。物品i的重量是wi,其价值为vi,背包的容量为C。问应如何选择装入背包的物品,使得装入背包中物品的总价值最大?0-1背包问题是一个特殊的整数规划问题。0-1背包问题设所给0-1背包问题的子问题的最优值为m(i,j),即m(i,j)是背包容量为j,可选择物品为i,i+1,…,n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质,可以建立计算m(i,j)的递归式如下。例子背包容量为9,要装入4个体积为2,3,4,5的物品,价值分别为3,4,5,7。voidknapsack(){inti,j;for(i=0;i<=c;++i)m[0][i]=0;for(i=0;i<=n;++i)m[i][0]=0;for(i=1;i<=n;++i)for(j=1;j<=c;++j){if(j<w[i])m[i][j]=m[i-1][j];elsem[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+w[i]);}}化简思考:需要这么多行么?intmVal,nVal;int*dp;intmax(inta,intb){ return(a>b?a:b);}voidZeroOnePack(intcost,intweight){ for(inti=nVal;i>=0;i--) dp[i]=max(dp[i],dp[i-cost]+weight);}intmain(intargc,char*argv[]){ mVal=4; nVal=9; intc[4]={2,3,4,5}; intw[4]={3,4,5,9};dp=newint[nVal+1];memset(dp,0,(nVal+1)*sizeof(int)); for(inti=0;i<mVal;i++) { ZeroOnePack(c[i],w[i]); } cout<<dp[nVal]<<endl;delete[]dp;return0;}再化简再思考:需要每次从nVal查到0么?voidZeroOnePack(intcost,intweight){ for(inti=nVal;i>=cost;i--) dp[i]=max(dp[i],dp[i-cost]+weight);}