#include <iostream>
void readdata();
void search(int);
void checkmax();
void printresult();
int W=17, n=5; //c： 背包容量；n：物品数
int w[5], v[5]; //w[i]、v[i]：第i件物品的重量和价值
int a[5], max; //a数组存放当前解各物品选取情况；max：记录最大价值
//a[i]=0表示不选第i件物品，a[i]=1表示选第i件物品
main()
{
readdata(); //读入数据
search(0); //递归搜索
printresult();
}
void search(int m)
{
if(m>=n)
checkmax(); //检查当前解是否是可行解，若是则把它的价值与max比较
else
{
a[m]=0; //不选第m件物品
search(m+1); //递归搜索下一件物品
a[m]=1; //选第m件物品
search(m+1); //递归搜索下一件物品
}
}
void checkmax()
{
int i, weight=0, value=0;
for(i=0;i<n;i++)
{
if(a[i]==1) //如果选取了该物品
{
weight = weight + w[i]; //累加重量
value = value + v[i]; //累加价值
}
}
if(weight<=W) //若为可行解
if(value>max) //且价值大于max
max=value; //替换max
}
void readdata()
{
int i;
cout<<"请输入各物品的重量:\n";
for(i=0;i<n;i++)
cin>>w[i];
cout<<endl;
cout<<"请输入各物品的价值:\n";
for(i=0;i<n;i++)
cin>>v[i];
cout<<endl;
}
void printresult()
{ int i;
cout<<"最优解为:\n";
for(i=0;i<n;i++)
cout<<a[i]<<'\t';
cout<<endl<<endl;
cout<<"max value="<<max<<endl<<endl;
}
