0-1背包问题的 栈式分支限界法 c++代码

0-1背包问题是一个经典的动态规划问题，它的主要思想是在背包容量有限的情况下，如何选取物品，使得背包中装入的物品价值最大。栈式分支限界法是一种解决0-1背包问题的有效算法，其主要思想是通过对问题状态空间树进行搜索，找到最优解。

以下是使用C++实现0-1背包问题的栈式分支限界法代码：

#include<iostream>
#include<algorithm>
using namespace std;

struct node
{
    int w,v;//物品重量和价值
    double p;//价值比
};

bool cmp(node a,node b)
{
    return a.p>b.p;//按价值比从大到小排序
}

int main()
{
    int n,m;
    cin>>n>>m;//输入物品数量和背包容量

    node *a=new node[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i].w>>a[i].v;
        a[i].p=double(a[i].v)/a[i].w;//计算价值比
    }

    sort(a,a+n,cmp);//按价值比从大到小排序

    double maxv=0;//最大价值
    int *x=new int[n];
    int *bestx=new int[n];//记录最优解
    for(int i=0;i<n;i++)
    {
        x[i]=0;//初始化x
        bestx[i]=0;//初始化bestx
    }

    int i=0;
    while(i!=-1)//循环终止条件
    {
        if(a[i].w>m-x[i])//如果当前物品放不下，跳过
        {
            i--;
            continue;
        }

        x[i]=1;//选中当前物品
        m-=a[i].w;//更新剩余容量
        maxv+=a[i].v;//更新最大价值

        if(i==n-1)//更新最优解
        {
            for(int j=0;j<n;j++)
                bestx[j]=x[j];
        }
        else//继续搜索下一个物品
        {
            i++;
            x[i]=0;
        }
    }

    cout<<"最大价值为："<<maxv<<endl;//输出结果
    cout<<"所选物品为：";
    for(int i=0;i<n;i++)
    {
        if(bestx[i]==1)
            cout<<i+1<<" ";
    }
    cout<<endl;

    delete[] a;
    delete[] x;
    delete[] bestx;
    return 0;
}