编辑代码

#include <iostream>
using namespace std;
 
#define N 999  
int w[N];    //重量
int v[N];    //价值
int x[N];     //x[i]=1：物品i放入背包，0代表不放入
int n,c;       //n：物品总数，c：背包的最大容量
int Weight=0;  //当前已放入背包的物品总重量
int Value=0;   //当前已放入背包的物品总价值
int BestValue=0;  //最优值；当前的最大价值，初始化为0
int BestX[N];       //最优解；BestX[i]=1代表物品i放入背包，0代表不放入
 
void input()
{
    cout<<"请输入物品的个数：";
    cin>>n;
    cout<<"请输入每个物品的重量及价值（如：2 3 表示重量2价值3的物品）:"<<endl;
    for(int i=1;i<=n;i++)
    {
        cin>>w[i]>>v[i];
    }
    cout<<"请输入背包容量：";
    cin>>c;
}
void output()
{
    cout<<"最优解是:"<<BestValue<<endl;
    cout<<"(";
    for(int i=1;i<=n;i++)
    cout<<BestX[i]<<" ";
    cout<<")";
    cout<<"按顺序依次表示各物品的数量"; 
 
}

void backtrack(int t)
{
    //叶子节点 
    if(t>n)
    {
        //如果存在更优解
        if(Value>BestValue)
        {
            //保存更优解
            BestValue=Value;
            for(int i=1;i<=n;++i)
            BestX[i]=x[i];
        }
    }
    else
    {
        //遍历当前节点的子节点：0 不放入背包，1放入背包
        for(int i=0;i<=1;++i)
        {
            x[t]=i;
 
            if(i==0) //不放入背包
            {
                backtrack(t+1);
            }
            else //放入背包
            {
                //约束条件：放的下
                if((Weight+w[t])<=c)
                {
                    Weight+=w[t];
                    Value+=v[t];
                    backtrack(t+1);
                    Weight-=w[t];
                    Value-=v[t];
                }
            }
        }
    }
 
 
}
 
int main(int argc, char*argv[])
{
    input();
    backtrack(1);
    output();
    return 0;
}