程序填空题：0/1背包问题（分支限界法）

0/1背包问题。给定一载重量为m的背包及n个重量为wi、价值为vi的物体，1≤i≤n,要求把物体装入背包，使背包的物体价值最大。

### 输入格式:

第一行输入背包载重量m及背包个数n，再依次输入n行，每行为背包重量wi和价值vi。

### 输出格式:

第一行输出输出所求X[n]数组，第二行输出装入背包内的物体的最大价值。

### 输入样例1:

```in
5 10
2 6
2 3
6 5
5 4
4 6
```

### 输出样例1:

```out
11001
15
```
### 输入样例2:

```in
5 10
11 2
13 10
12 5
13 3
11 6
```

### 输出样例2:

```out
00
0
```


```c++
#include
#include
#include
using namespace std;
#define MAXN 20 //最多可能物品数
//问题表示
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+1]; //当前结点包含的解向量
double ub; //上界
};

void bound(NodeType &e) //计算分枝结点e的上界
{
int i=e.i+1;
int sumw=e.w;
double sumv=e.v;
while ()
{ sumw+=w[i]; //计算背包已装入载重
sumv+=v[i]; //计算背包已装入价值
i++;
}
if (i<=n)
e.ub=;
else
e.ub=sumv;
}

void EnQueue(NodeType e,queue &qu) //结点e进队qu
{
if (e.i==n) //到达叶子结点
{
if (e.v>maxv) //找到更大价值的解
{
;
for (int j=1;j<=n;j++)
;
}
}
else qu.push(e); //非叶子结点进队
}
void bfs() //求0/1背包的最优解
{
int j;
NodeType e,e1,e2; //定义3个结点
queue qu; //定义一个队列
e.i=0; //根结点置初值，其层次计为0
e.w=0; e.v=0;
e.no=total++;
for (j=1;j<=n;j++)
e.x[j]=0;
bound(e); //求根结点的上界
qu.push(e); //根结点进队
while (!qu.empty()) //队不空循环
{
e=qu.front(); qu.pop(); //出队结点e
e1.no=total++;
e1.i=e.i+1; //建立左孩子结点
e1.w=e.w+w[e1.i];
e1.v=e.v+v[e1.i];
for (j=1;j<=n;j++) //复制解向量
e1.x[j]=e.x[j];
e1.x[e1.i]=1;
bound(e1); //求左孩子结点的上界
if () //剪枝：检查左孩子结点
{
EnQueue(e1,qu); //左孩子结点进队操作
}
e2.no=total++; //建立右孩子结点
e2.i=e.i+1;
e2.w=;
e2.v=;
for (j=1;j<=n;j++) //复制解向量
e2.x[j]=e.x[j];
e2.x[e2.i]=;
bound(e2); //求右孩子结点的上界
if () //若右孩子结点可行,则进队,否则被剪枝
EnQueue(e2,qu);
}
}
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]);
printf("\n%d",maxv);
return 0;
}
```






答案：
第1空：(sumw+w[i]<=W) && i<=n

第2空：sumv+(W-sumw)*v[i]/w[i]

第3空：maxv=e.v

第4空：bestx[j]=e.x[j]

第5空：e.w+w[e.i+1]<=W&&e1.ub>maxv

第6空：e.w

第7空：e.v

第8空：0

第9空：e2.ub>maxv