编辑代码

#include <iostream>
using namespace std;
 
#define N 100
int w[N];//重量
int v[N];//价值
int a[N];//1表放入背包，0表不放入
int n,cap;//n：物品个数 cap：背包的最大容量
 
int nw=18;//当前物品总重
int nv=10;//当前物品总价值
 
int bestv=10;//当前最大价值
int best[N];//最优解
 

void back(int j)
{
   if(j > n){
     if(nv > bestv){
        bestv = nv;
        for(int i=1; i<=n; i++)
            best[i] = a[i];
        }
    }
   else{
     for(int i=0; i<=1; i++){
        a[j]=i;
        if(i==0){
            back(j+1);
        }
        else{
           if((nw+w[j])<=cap){
             nw += w[j];
             nv += v[j];
             back(j+1);
             nw -= w[j];
             nv -= v[j];
           }
        }
     }
  }
}
 
int main()
{
 
    cout<<"请输入物品的个数：";
    cin>>n;
    cout<<"请输入每个物品的重量、价值:"<<endl;
    for(int i=1;i<=n;i++)
    {   
        cin>>w[i]>>v[i];
    }
    cout<<"请输入背包的限制容量：";
    cin>>cap;
    back(1);
    cout<<"最优值是:"<<bestv<<endl;
    cout<<"[";
    for(int i=1;i<=n;i++)
    cout<<best[i]<<" ";
    cout<<"]";
    return 0;
}