/*
课本 0-1背包 加上体积限制。
程序功能：将物体只能一次放入包中，要不超过总量、总体积且
价值最大

经过vc8.0编译通过
*
*/
#include <iostream>
#include <iomanip>
using namespace std;
#define N 10     //物品的可选数量

#define C 40     //包的最大可容纳重量
#define E   28     //包的最大可容纳体积

//动态规划算法
void knapsack(int * v,int *w,int wlength,int c,int *e,int ee,int (*m)[C+1][E+1])
{
int n=wlength-1;
//—————————————–
//递归计算的第一步
//求出当物品只有n的解
int jmax  = std::min(w[n]-1,c);
int jmax2 = std::min(e[n]-1,ee);

for(int j=0;j<=jmax;j++)
for(int k=0;k<=jmax2;k++)
m[n][j][k] = 0;

for(int j=w[n];j<=c;j++)
for(int k=e[n];k<=ee;k++)
m[n][j][k] = v[n];
//—————————————

//—————————————-
//计算其他
for(int i=n-1;i>=0;i–)
{
jmax = std::min(w[i]-1,c);
jmax2= std::min(e[i]-1,ee);
for(int j=0;j<=jmax;j++)
for(int k=0;k<=jmax2;k++)
m[i][j][k] = m[i+1][j][k];
for(int j=w[i];j<=c;j++)
for(int k=e[i];k<=ee;k++)
m[i][j][k] = std::max(m[i+1][j][k],m[i+1][j-w[i]][k-e[i]]+v[i]);
}

/*m[0][c][ee]=m[1][c][ee];
if(c>=w[1]&&ee>=e[1])
m[0][c][ee]=std::max(m[2][c][ee],m[2][c-w[1]][ee-e[1]]+v[1]);*/
}

void traceback(int (*m)[C+1][E+1],int *w,int ee,int *e,int wlength,int c,int *x)
{
int n=wlength-1;
for(int i=0;i<n;i++)
{
//cout<<setw(4)<<m[i][c][ee];
if(m[i][c][ee]==m[i+1][c][ee]) x[i]=0;
else
{
x[i]=1;
c-=w[i];
ee-=e[i];
}
}
//cout<<setw(4)<<m[n][c][ee];
x[n]=(m[n][c][ee]>0)?1:0;

}

int main()
{

int v[N]={ 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; //可选物品列表
int w[N]={ 1,  2, 3, 4, 5, 6, 7, 8, 9, 10}; //总量列表
int e[N]={ 1,  5, 6, 4, 2, 3, 7, 8, 9, 11}; //质量列表

int   m[N][C+1][E+1];     //用于计算的数组

int x[N];
knapsack(v,w,N,C,e,E,m);

traceback(m,w,E,e,N,C,x);
int weigth=0;
int volume=0;
cout<<“包的要求总质量”<<C<<”  总体积”<<E<<endl;
cout<<“____________选择的物品___________________”<<endl;
for(int i=0;i<N;i++)
if(x[i])
{
cout<<i<<“质量”<<w[i]<<“体积”<<e[i]<<“价值”<<v[i]<<endl;
weigth+=w[i];
volume+=e[i];
}
cout<<“_______________________________________”<<endl;
cout<<“装入后总质量:”<<weigth<<”  总体积:”<<volume;

return 0;
}