学步园

问题描述：

给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包容量为c。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。因此，该问题称为0-1背包问题。

DP思想：

首先物品个数为n个， 包总容量为c, 其中w[],v[]分别为n个物品的重量、价格。表m(i,j)表示从第i个物品开始容量为j的包的最大价值量。具体流程如下：

1. 初始化,当i=n-1时，若c>=w[i],则m(i,c)=v[i]；若0<=j<w[i]，则m(i,c)=0
2. 当0<=i<n-1时，若j>=w[i],则m(i,j)=max{ m(i+1,j), m(i+1,j-w[i])+v[i] }；若0<=j<w[i]，则m(i,j)=m(i+1,j)

C++源码：

#include <iostream><br /> #include <cstring><br /> using namespace std;</p> <p>class knap{<br /> public:<br /> knap();<br /> void init();<br /> int run();<br /> void dumpW();<br /> void dumpV();<br /> void dumpTable();<br /> void dumpTrace();<br /> int getCap();<br /> int getNum();<br /> private:<br /> void trace();<br /> const static int NUM_OF_GOODS = 256;<br /> const static int CAPACITY = 256;<br /> int w[NUM_OF_GOODS];//weight<br /> int v[NUM_OF_GOODS];//value<br /> int c;//capacity<br /> int num;//num of goods<br /> int table[NUM_OF_GOODS][CAPACITY];<br /> bool isIn[NUM_OF_GOODS];<br /> };</p> <p>knap::knap(){<br /> memset(w, 0, sizeof(w));<br /> memset(v, 0, sizeof(v));<br /> memset(table, 0, sizeof(table));<br /> memset(isIn, 0, sizeof(isIn));<br /> num = c = 0;<br /> }</p> <p>void knap::init(){<br /> num = 5;<br /> c = 10;<br /> w[0] = 1 , w[1] = 3, w[2] = 2, w[3] = 9, w[4] = 4;<br /> v[0] = 10, v[1] = 5, v[2] = 6, v[3] = 8, v[4] = 7;<br /> }<br /> int knap::run(){<br /> for(int i=0;i<=c;i++){<br /> if(w[num-1]<=i)<br /> table[num-1][i] = v[num-1];<br /> else<br /> table[num-1][i] = 0;<br /> }<br /> for(int i=num-2;i>=0;i--){<br /> for(int j=0;j<=c;j++){<br /> if(j>=w[i]){<br /> table[i][j]=max(table[i+1][j], table[i+1][j-w[i]]+v[i]);<br /> }else{<br /> table[i][j]=table[i+1][j];<br /> }<br /> }<br /> }<br /> this->trace();<br /> return table[0][c];<br /> }<br /> void knap::trace(){<br /> int curCap = c;<br /> for(int i=0;i<num-1;i++){<br /> if(table[i][curCap]==table[i+1][c])<br /> isIn[i] = false;<br /> else{<br /> isIn[i] = true;<br /> curCap -= w[i];<br /> }<br /> }<br /> isIn[num-1] = curCap >= w[num-1] ? true : false;<br /> }<br /> void knap::dumpW(){<br /> for(int i=0;i<num;i++){<br /> cout << w[i] << "/t";<br /> }<br /> cout << endl;<br /> }<br /> void knap::dumpV(){<br /> for(int i=0;i<num;i++){<br /> cout << v[i] << "/t";<br /> }<br /> cout << endl;<br /> }<br /> void knap::dumpTable(){<br /> for(int i=num-1;i>=0;i--){<br /> for(int j=0;j<=c;j++)<br /> cout << table[i][j] << "/t";<br /> cout << endl;<br /> }<br /> }<br /> void knap::dumpTrace(){<br /> for(int i=0;i<num;i++){<br /> cout << isIn[i] << "/t";<br /> }<br /> cout << endl;<br /> }<br /> int knap::getCap(){<br /> return c;<br /> }<br /> int knap::getNum(){<br /> return num;<br /> }<br /> int main()<br /> {<br /> knap k;<br /> int ans;</p> <p> k.init();<br /> ans = k.run();<br /> cout << "Num of goods:/t" << k.getNum() << endl;<br /> cout << "Capacity:/t" << k.getCap() << endl;<br /> cout << "Weight:/n";<br /> k.dumpW();<br /> cout << "Value:/n";<br /> k.dumpV();<br /> cout << "Table:/n";<br /> k.dumpTable();<br /> cout << "Trace:/n";<br /> k.dumpTrace();<br /> cout << "answer:/n" << ans << endl;</p> <p> return 0;<br /> }<br />

运行结果：