现有n种物品,对1<=i<=n,已知第i种物品的重量为正整数Wi,价值为正整数Vi,背包能承受的最大载重量为正整数W,现要求找出这n种物品的一个子集,使得子集中物品的总重量不超过W且总价值尽量大。(注意:这里对每种物品或者全取或者一点都不取,不允许只取一部分).
\#include "stdafx.h"\
\
const int C\_MaxNum = 15;\
const int C\_MaxCapacity = 100;\
int C[C\_MaxNum + 1][C\_MaxCapacity + 1];\
\
int Knapsack( int m, int n ){\
int \*w = new int[n + 1];\
int \*v = new int[n + 1];\
int \*x = new int[n + 1];\
\
cout \<\< "input " \<\< n \<\< " [weight and value] separately\\n";\
for( int i = 1; i \<= n; i++ )\
cin \>\> w[i] \>\> v[i];\
\
// i: number.\
// j: mass.\
for( int i = 1; i \<= n; i++ )\
for( int j = 1; j \<= m; j++ )\
{\
if( w[i] \> j )\
{\
// 无法装进,所以跟i-1个物品的价值是一样的.\
C[i][j] = C[i - 1][j];\
}\
else if( w[i] \<= j )\
{\
//可以装进\
// C[i - 1][j]: i-1个物品,未装进.\
// C[i - 1][j - w[i]] + v[i]: 可以装进第i个物品.\
// 选其中大者.\
C[i][j] = std::max(C[i - 1][j], C[i - 1][j - w[i]] + v[i]);\
}\
}\
\
int j = m;\
for( int i = n; i \>= 1; i-- ){\
if( C[i][j] \> C[i - 1][j] ){\
x[i] = 1;\
j -= w[i];\
}\
else\
x[i] = 0;\
}\
cout \<\< "Have chosen knapsack:\\n";\
copy( &x[1], &x[n + 1], ostream\_iterator\<int\>(cout, " ") );\
cout \<\< "\\n C[n][m]:\\n";\
for( int i = 1; i \<= n; i++ ){\
for( int j = 1; j \<= m; j++ )\
cout \<\< std::setw(3) \<\< C[i][j] \<\< " ";\
cout \<\< endl;\
}\
delete []w;\
delete []v;\
delete []x;\
return C[n][m];\
}\
\
int main(){\
int n, m;\
cout \<\< "input 背包承受的质量m and 物体总共的数量n:\\n";\
cin \>\> m \>\> n;\
cout \<\< "knapsack's optimal solution is:" \<\< Knapsack( m, n ) \<\< endl;\
}\
/\*\
Sample output:\
input 背包承受的质量m and 物体总共的数量n:\
18 7\
input 7 [weight and value] separately\
11 7\
2 8\
4 8\
8 12\
9 13\
6 4\
10 14\
Have chosen knapsack:\
0 1 1 0 0 0 1\
C[n][m]:\
0 0 0 0 0 0 0 0 0 0 7 7 7 7 7 7 7 7\
0 8 8 8 8 8 8 8 8 8 8 8 15 15 15 15 15 15\
0 8 8 8 8 16 16 16 16 16 16 16 16 16 16 16 23 23\
0 8 8 8 8 16 16 16 16 20 20 20 20 28 28 28 28 28\
0 8 8 8 8 16 16 16 16 20 21 21 21 28 29 29 29 29\
0 8 8 8 8 16 16 16 16 20 21 21 21 28 29 29 29 29\
0 8 8 8 8 16 16 16 16 20 21 22 22 28 29 30 30 30\
knapsack's optimal solution is:30\
请按任意键继续. . .\
\*/
\#include "stdafx.h"\
\
int Knapsack( int m, int n ){\
int \*w = new int[n + 1];\
int \*v = new int[n + 1];\
\
cout \<\< "input " \<\< n \<\< " [weight and value] separately\\n";\
for( int i = 0; i \< n; i++ )\
cin \>\> w[i] \>\> v[i];\
\
\
int \*leftWeigh = new int[m + 1];\
int nMaxValue = std::numeric\_limits\<int\>::min();\
memset( leftWeigh, 0, sizeof(int)\*(m+1) );\
\
// [i] 物品为0\~i时,求出可达质量.\
for( int i = 0; i \< n; i++ )\
{\
for( int j = w[i]; j \<= m; j++ )\
{\
leftWeigh[j-w[i]] = std::max( leftWeigh[j] + v[i], leftWeigh[j-w[i]] );\
if( nMaxValue \< leftWeigh[j-w[i]] )\
nMaxValue = leftWeigh[j-w[i]];\
}\
}\
\
delete []w;\
delete []v;\
delete []leftWeigh;\
return nMaxValue;\
}\
\
int main(){\
int n, m;\
cout \<\< "input 背包承受的质量m and 物体总共的数量n:\\n";\
cin \>\> m \>\> n;\
cout \<\< "knapsack's optimal solution is:" \<\< Knapsack( m, n ) \<\< endl;\
}\
/\*\
input 背包承受的质量m and 物体总共的数量n:\
18 7\
input 7 [weight and value] separately\
11 7\
2 8\
4 8\
8 12\
9 13\
6 4\
10 14\
knapsack's optimal solution is:30\
请按任意键继续. . .\
\*/