#include<iostream>
using namespace std;
//动态规划实现0-1背包客问题
#define C 40
#define MYNUM 10//第0个不算物品，实际有n-1个物品
int m[MYNUM][C];
typedef struct{
int w,v;
}Elem;
typedef struct{
Elem* arr;
int length;
}SqList;
void findPath(SqList L,int n,int c){
if(m[n][c]!=m[n-1][c]){
cout<<"装载的第"<<n<<"个，值为："<<L.arr[n].v<<endl;
c=c-L.arr[n].w;
}
if(n-1>0)findPath(L,n-1,c);
}
void backpacker(SqList L){
for(int i=0;i<MYNUM;++i)for(int j=0;j<=C;++j)m[i][j]=0;
for(int i=1;i<MYNUM;++i)
for(int j=1;j<=C;++j)
if(j<L.arr[i].w)m[i][j]=m[i-1][j];
else m[i][j]=max(m[i-1][j],m[i-1][j-L.arr[i].w]+L.arr[i].v);
cout<<"装载最多价值为："<<m[MYNUM-1][C]<<endl;
findPath(L,MYNUM-1,C);
}
int main(){
SqList L;
L.arr=new Elem[MYNUM];
int ev[MYNUM]={0,4,2,3,5,3,6,9,8,7},ew[MYNUM]={0,2,9,5,3,1,7,1,8,7};
for(int i=0;i<MYNUM;++i){
L.arr[i].v=ev[i];
L.arr[i].w=ew[i];
}
backpacker(L);
return 0;
}