#include <iostream>
using namespace std;
#define N 20
int w[]={6,5,4,2,1};
int v[]={5,3,5,3,2};
int X[N];
int c=10,n=4;
int cw=0,cv=0;
int maxv=0;
int maxX[N];
void backtrack(int j)
{
if(j>n)
{
if(cv>maxv)
{
maxv=cv;
for(int i=1;i<=n;i++)
maxX[i]=X[i];
}
}
else
{
for(int i=0;i<=1;i++)
{
X[j]=i;
if(i==0)
{
backtrack(j+1);
}
else
{
if((cw+w[j])<=c)
{
cw+=w[j];
cv+=v[j];
backtrack(j+1);
cw-=w[j];
cv-=v[j];
}
}
}
}
}
int main()
{
cout<<"请输入物品的个数:"<<n<<endl;
for(int i=1;i<=n;i++)
cout<<"请输入每个物品的重量及价值:"<<w[i]<<v[i]<<endl;
cout<<"请输入背包的限制容量:"<<c<<endl;
backtrack(1);
cout<<"最优值是:"<<maxv<<endl;
return 0;
}