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

经过vc8.0编译通过
*
*/

#include <iostream>
using namespace std;
#define N 10
#define C 50
void knapsack(int * v,int *w,int wlength,int c,int(*m)[C+1])
{
int n=wlength-1;
int jmax=std::min(w[n]-1,c);
for(int j=0;j<=jmax;j++)
m[n][j]=0;
for(int j=w[n];j<=c;j++)
m[n][j]=v[n];
for(int i=n-1;i>1;i–)
{
jmax=std::min(w[i]-1,c);
for(int j=0;j<=jmax;j++)
m[i][j]=m[i+1][j];
for(int j=w[i];j<=c;j++)
m[i][j]=std::max(m[i+1][j],m[i+1][j-w[i]]+v[i]);
}
m[1][c]=m[2][c];
if(c>=w[1])
m[1][c]=std::max(m[1][c],m[2][c-w[1]]+v[1]);
}

void traceback(int (*m)[C+1],int *w,int wlength,int c,int *x)
{
int n=wlength-1;
for(int i=1;i<n;i++)
if(m[i][c]==m[i+1][c]) x[i]=0;
else
{
x[i]=1;
c-=w[i];
}
x[n]=(m[n][c]>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 m[N][C+1];
int x[N];
knapsack(v,w,N,C,m);

traceback(m,w,N,C,x);
int weigth=0;
for(int i=0;i<N;i++)
if(x[i])
{
cout<<w[i]<<endl;
weigth+=w[i];
}
cout<<weigth;
float j=1.0;
int i = 0.7;
return 0;
}