#include "oneZeroPackage_Optimize.h"int oneZeropkt_optimizeint(int pktVolum,int *prtVolum,int *prtValue,int prtLen){struct Goods_op *goods=new Goods_op[prtLen+1];for(int i=1;i<=prtLen; i++){goods[i].value=prtValue[i];goods[i].volum=prtVolum[i];}int *select=new int[pktVolum+1];for(int i=0;i<=pktVolum;i++){select[i]=0;}for(int i=1;i<=prtLen; i++){for(int w=pktVolum; w>=goods[i].volum; w--){//注意我们是在前一次的基础上进行这一次的计算select[w]=Max((select[w]),(select[w-goods[i].volum]+goods[i].value));}}return select[pktVolum];}
#ifndef ONE_ZERO_PACKAGE_OPTIMIZE_H#define ONE_ZERO_PACKAGE_OPTIMIZE_H#define Max(a,b) a>b? a:bstruct Goods_op{int value;int volum;};int oneZeropkt_optimizeint(int pktVolum,int *prtVolum,int *prtValue,int prtLen);#endif
#include"oneZeroPackage.h"#include<iostream>#include"oneZeroPackage_Optimize.h"int main(){int prtValue[4]={0,6,10,12};int prtVolum[4]={0,1,2,3};//std::cout<<oneZeropkt(5,prtVolum,prtValue,3)<<std::endl;std::cout<<oneZeropkt_optimizeint(5,prtVolum,prtValue,3)<<std::endl;}
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; 也就是根据i-1的计算结果来计算第i次的计算结果。原文：http://www.cnblogs.com/yml435/p/4655567.html