编辑代码

#include <iostream>
using namespace std;
 
#define N 100   
int w[N];  
int v[N];    
int x[N];    
int n,c;    
int CurWeight = 0;  
int CurValue = 0; 
int BestValue = 0;  
int BestX[N];     
 
void input()
{
    cout<<"请输入物品的个数："<<endl;
    cin>>n;
    cout<<"请输入每个物品的重量及价值(如12 22):"<<endl;
    for(int i = 1; i <= n; i++)
    {
        cin>>w[i]>>v[i];
    }
    cout<<"请输入背包的容量："<<endl;
    cin>>c;
}
void output()
{
    cout<<"最优值是:"<<BestValue<<endl;
    cout<<"(";
    for(int i=1;i<=n;i++)
        cout<<BestX[i]<<" ";
    cout<<")";
 
}

void backtrack(int t)
{

    if(t>n)
    {
   
        if(CurValue>BestValue)
        {
      
            BestValue = CurValue;
            for(int i=1; i<=n; ++i)
                BestX[i] = x[i];
        }
    }
    else
    {
     
        for(int i=0; i<=1; ++i)
        {
            x[t]=i;
 
            if(i==0)
            {
                backtrack(t+1);
            }
            else 
            {
                if((CurWeight+w[t])<=c)
                {
                    CurWeight += w[t];
                    CurValue += v[t];
                    backtrack(t+1);
                    CurWeight -= w[t];
                    CurValue -= v[t];
                }
            }
        }
    }
 
 
}
 
int main(int argc, char* argv[])
{
 
    input();
    backtrack(1);
    output();
    return 0;
}