第2章　背包问题

2.1　简单背包问题

【题目描述】 简单背包问题（Backpack）

一个背包可以放入的物品的最大质量为S。现有N个物品，它们的质量均为正整数，分别为W₁,W₂,W₃,…,W_N。从N个物品中挑选若干个放入背包，使得它们的质量之和正好为S。若成功，则输出放入背包的各个物品的质量，否则输出“Failed!”。

【输入格式】

第一行为两个整数，即S和N（S＜1 000，N＜32）。第二行为N个整数，即N个物品各自的质量。

【输出格式】

若成功（答案非唯一），则输出放入背包的各个物品的质量，一个物品的质量占一行；否则输出“Failed!”。

【输入样例】

10 5

1 2 3 4 5

【输出样例】

1

4

5

【算法分析】

容易想到的方法是将物品逐个放入背包内试验，设布尔函数Bag(s,n)表示从剩下的n个物品中寻找合适的物品放入剩余可容纳质量为s的背包，如果有解返回1，否则返回0。

从取最后一个物品开始：

（1）取最后一个物品W_n，调用Bag(s,n)；

（2）如果 W_n=s，则结束程序，输出结果；

（3）如果 W_n＜s，且n＞1，则求Bag(s-W_n,n-1)；

（4）如果 W_n＞s，且n＞1，则删除W_n，从剩下的n-1个物品中继续找，即求Bag(s,n-1)。

递归结束的条件如下：

（1）W_n=s（放入物品的质量正好等于背包剩下能装的质量）；

（2）W_n≠s（无解）；

（3）n≤0（没有物品可试）。

但实际上问题并不是这么简单，因为由选取并放入物品的质量很可能无法获得正确的结果。例如s=10，物品的质量分别为1、6、2、7和5，如果第一次选择W_n=5的物品放入背包，则后面再怎么选择也不可能成功。正确的做法是排除W_n=5的物品，从W_n=7的物品开始选择才可能有正确答案，即7+2+1=10。

因此W_n是否有效还要看后续的Bag(s-W_n,n-1)是否有解。如果无解，说明先前选取的W_n不合适，就要放弃W_n，在剩余物品中重新开始挑选，即求Bag(s,n-1)。

参考代码如下。

 1    //简单背包问题 —— 递归算法
 2    #include <bits/stdc++.h>
 3    using namespace std;
 4
 5    int W[40];                       //各物品的质量
 6
 7    int Bag(int s,int n)             //s为剩余质量，n为剩余可选物品的数量
 8    {
 9      if(s==0)                       //如果剩余质量正好为0，则成功
10        return 1;
11      if(s<0 || (s> 0 && n<1)) //如果s<0或n<1，则不成功
12        return 0;
13      if(Bag(s-W[n],n-1))            //从后往前装，装上W[n]后，若剩余物品仍有解
14      {
15        cout<<W[n]<<"\n";           //则装进第n个包，并输出
16        return 1;
17      }
18      return Bag(s,n-1);             //如果装了第n个后无解则删除，尝试装第n-1个
19    }
20
21    int main()
22    {
23      int S,N;
24      scanf("%d%d",&S,&N);
25      for(int i=1; i<=N; ++i)
26        scanf("%d",&W[i]);
27      if(!Bag(S,N))
28        printf("Failed!\n");
29      return 0;
30    }

简单背包问题使用递归算法枚举了可能的组合，每一个枚举的物品有放和不放两种情况，其实现代码中已经隐含了接下来要讲到的0/1背包问题的算法设计思想。