//采用队列式分枝限界法求解0/1背包问题的算法 #include <stdio.h> #include <queue> #include <iostream> using namespace std; #define MAXN 20 //最多可能物品数 #define INF 0x3f3f3f3f3 //定义∞ //问题表示 int n,W; int w[MAXN+1]; //重量，下标0不用 int v[MAXN+1]; //价值，下标0不用 //求解结果表示 int maxv=-9999; //存放最大价值,全局变量 int bestx[MAXN+1]; //存放最优解,全局变量 int total=1; //解空间中结点数累计,全局变量 struct NodeType //队列中的结点类型 { int no; //结点编号 int i; //当前结点在搜索空间中的层次 int w; //当前结点的总重量 int v; //当前结点的总价值 int x[MAXN]; //当前结点包含的解向量 double ub; //上界 bool operator<(const NodeType &s) const //重载<关系函数 { return ub<s.ub; //ub越大越优先出队 } }; void bound(NodeType &e); //计算分枝结点e的上界 void EnQueue(NodeType e,priority_queue<NodeType> &qu); //结点e进队qu void bfs(); //求0/1背包的最优解 int main() { cin>>n>>W; //输入物体个数及背包载重量 for(int i=1;i<=n;i++)//输入各物体重量及价值 cin>>w[i]>>v[i]; bfs(); //调用队列式分枝限界法求0/1背包问题 for(int i=1;i<=n;i++) printf("%d",bestx[i]); //输出所求X[n]数组 printf("\n%d",maxv); return 0; } /* 请在这里填写答案 */

答案：

//采用队列式分枝限界法求解0/1背包问题的算法
#include <stdio.h>
#include <queue>
#include <iostream>
using namespace std;

#define MAXN 20                        //最多可能物品数
#define INF 0x3f3f3f3f3                //定义∞

//问题表示
int n,W;
int w[MAXN+1];                //重量，下标0不用
int v[MAXN+1];                  //价值，下标0不用

//求解结果表示
int maxv=-9999;                        //存放最大价值,全局变量
int bestx[MAXN+1];                    //存放最优解,全局变量
int total=1;                        //解空间中结点数累计,全局变量

struct NodeType                        //队列中的结点类型
{
    int no;                            //结点编号
    int i;                            //当前结点在搜索空间中的层次
    int w;                            //当前结点的总重量
    int v;                            //当前结点的总价值
    int x[MAXN];                    //当前结点包含的解向量
    double ub;                        //上界

    bool operator<(const NodeType &s) const    //重载<关系函数
    {
        return ub<s.ub;                //ub越大越优先出队
    }
};

void bound(NodeType &e);            //计算分枝结点e的上界
void EnQueue(NodeType e,priority_queue<NodeType> &qu);    //结点e进队qu
void bfs();                    //求0/1背包的最优解

int main() {
    cin>>n>>W; //输入物体个数及背包载重量
    for(int i=1;i<=n;i++)//输入各物体重量及价值
        cin>>w[i]>>v[i];
    bfs();                    //调用队列式分枝限界法求0/1背包问题
    for(int i=1;i<=n;i++)
        printf("%d",bestx[i]);        //输出所求X[n]数组
    printf("\n%d",maxv);
    return 0;
}

void bound(NodeType &e){
    int i=e.i+1;
    int wt=e.w;
    double bound=e.v;
    while(i<=n && wt+w[i]<=W){
        wt+=w[i];
        bound+=v[i];
        i++;
    }
    if(i<=n){
        bound+=(W-wt)*(v[i]*1.0/w[i]);
    }
    e.ub=bound;
}

void EnQueue(NodeType e, priority_queue<NodeType> &qu){
    if(e.i==n){
        if(e.v>maxv){
            maxv=e.v;
            for(int j=1;j<=n;j++){
                bestx[j]=e.x[j];
            }
        }
        return;
    }
    NodeType e1=e,e2=e;
    e1.x[e.i+1]=0;
    bound(e1);
    if(e1.ub>maxv){
        e1.i=e.i+1;
        EnQueue(e1,qu);
    }
    e2.x[e.i+1]=1;
    bound(e2);
    if(e2.ub>maxv){
        e2.i=e.i+1;
        e2.v=e.v+v[e.i+1];
        e2.w=e.w+w[e.i+1];
        EnQueue(e2,qu);
    }
}

void bfs(){
    priority_queue<NodeType> qu;
    NodeType e;
    e.i=0;
    e.w=0;
    e.v=0;
    bound(e);
    qu.push(e);
    while(!qu.empty()){
        e=qu.top();
        qu.pop();
        total++;
        EnQueue(e,qu);
    }
}