#define M 20
using namespace std;
int w[M],p[M],bestx[M],x[M]; //x[]暂存
int n,bestP=0; //表示当前背包获得的最大价值
int C;
//将单位重量的物品按降序排
void sort(int n){int flag,index;
for(int i=1;i<n;i++){
index=i;
for(int j=i+1;j<=n;j++){
if((float)p[j]/w[j]>(float)p[index]/w[index]) {index=j;} //此处防止当出现小数时，整型相除会将小数去除
}
if(index!=i){
flag=w[i];
w[i]=w[index];
w[index]=flag;
flag=p[i];
p[i]=p[index];
p[index]=flag;
}
}
}
void BackTrack(int i,int cp,int cw){
if(i>n){ //到达叶子节点
if(bestP<cp) bestP=cp;
for(i=0;i<=n;i++) bestx[i]=x[i];
}
else{
for(int j=0;j<=1;j++)
{
x[i]=j;
if(cw+x[i]*w[i]<=C)
{
cw+=w[i]*x[i];
cp+=p[i]*x[i];
BackTrack(i+1,cp,cw);
cw-=w[i]*x[i];
cp-=p[i]*x[i];
}
}
}
}
void main(){
int cw=0; //背包当前的重量
int cp=0; //背包当前获得的价值
//物品的重量存储在数组w[n]中，价值存储在数组p[n]中,bestx是否有装入背包。
cout<<"请输出背包的最大容量:";
cin>>C;
//输入重量与价值
cout<<"请输入物品的数量:";
cin>>n;
for(int i=1;i<=n;i++){
cout<<"第"<<i<<"件物品的重量 价值:";
cin>>w[i];
cin>>p[i];
x[i]=bestx[i]=0;
}
//按单位价值排序
sort(n);
BackTrack(1,cp,cw);
cout<<"最大价值"<<bestP<<endl;
cout<<"放入的物品的重量为:";
for(int j=1;j<=n;j++){
if(bestx[j]==1)
cout<<w[j]<<" ";
}
cout<<endl;
}