背包问题（二维数组解法）
参考文章：
http://www.cnblogs.com/Anker/archive/2013/05/04/3059070.html
对于背包问题的解答又冒出一个新的解法，这是一种自顶向下的解法：
设一个二维数组select[i][v]表示的是，将前i个物品放入到容量为v的背包中所能得到的最大价值。如果使用递归的算法
如何使这人问题转换为多个子问题呢，也就是对这个问题进行不停地分解，直到可以求解为止，然后“归”，也就是子
问题都求解了，然后将这些子问题拼凑成大问题，因为大问题是依赖于子问题的。
#include<iostream>#include<string>const int N=3; //物品个数const int W=50; //背包的容量struct Product{ int value; int weight;}; Product goods[N+1]={{0,0},{60,10},{100,20},{120,30}};//商品信息int select[N+1][W+1]; int pktProb(){ for(int w=1;w<W; w++){ select[0][w]=0; } for(int i=1;i<=N; i++){ select[i][0]=0; //背包容量为0时，最大价值为0，初使化 for(int w=1; w<=W; w++){//考虑背包容量从1到W的子问题，在子问题的基础上求背包容量为W时的价值 if(goods[i].weight<=w){//这里需要进行选择，只有当当前商品重量比包背的容量小时。 if(select[i-1][w-goods[i].weight]+goods[i].value>select[i-1][w]){ select[i][w]=goods[i].value+select[i-1][w-goods[i].weight]; }else{ select[i][w]=select[i-1][w]; } }else{ select[i][w]=select[i-1][w]; //则进行初使化 } } } return select[N][W]; }
如上代码所示，先首新建了一个select[N+1][W+1]大小的数组，用于对子问题进行求解。
对每一个物品进行循环，而在选择这些物品的时候，对背包的容量进行循环，求得在前
i个物品的情况下，所能得到的最大的价值。一定要胆白select[i][v]是前面i个商品在容量
为v的情况下所能获得的最大的价值，当然有时候并不需要那么大的容量。
int
select[N+1][W+1];这里我们可以看到，我们将数组设为N+1和M+1维的情况，是因为我们把背包的容量为0和商品数为0时这些特殊情况
考虑进去了。
select
[
i
][
0
]=
0
;这里可以看到，这里初使化为0的根据是当容量为0时，肯定是为0的。
for(int w=1;w<W; w++){
//这里做的目的是，我们考虑当商品数为0时，它的价值肯定是为0的。
select[0][w]=0;
}
#include"oneZeroPackage.h"/*函数入口参数： pktVolum：背包的容量 prtVolum：物品的体积 prtValue: 物品的价值 prtLen : 物品的个数测试代码： int prtValue[4]={0,6,10,12}; int prtVolum[4]={0,1,2,3}; std::cout<<oneZeropkt(5,prtVolum,prtValue,3)<<std::endl; */int oneZeropkt(int pktVolum,int *prtVolum,int *prtValue,int prtLen){ struct Goods *goods=new Goods[prtLen+1]; int select[500][500]; for(int i=1;i<=prtLen; i++){ goods[i].value=prtValue[i]; goods[i].volum=prtVolum[i]; } for(int w=1;w<=pktVolum; w++){ //这个表示在背包有没有任何商品可选的情况下它的价值为0 select[0][w]=0; } for(int i=1; i<=prtLen;i++){ select[i][0]=0; //这个表示在背包的容量为0的情况下它的价值为0 for(int w=1; w<=pktVolum;w++){ if(w>=goods[i].volum){ if(select[i-1][w-goods[i].volum]+goods[i].value>select[i-1][w]){ select[i][w]=select[i-1][w-goods[i].volum]+goods[i].value; }else{ select[i][w]=select[i-1][w]; } }else{ select[i][w]=select[i-1][w]; } } } return select[prtLen][pktVolum]; }
来自为知笔记(Wiz)
附件列表
转载于:https://www.cnblogs.com/yml435/p/4655570.html
