11.3著名的背包问题
背包问题是一个经典的动态规划求解问题。它既简单形象、容易理解，又在某种程度上能够揭示动态规划的本质。在很多地方都可以看到这类问题的描述，下面我们来讨论这个问题。
11.3.1 什么是背包问题
背包问题是一个求某种组合优化的问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。
先来看一个背包问题的具体案例描述。
现在有一个背包，最多只能装重量8公斤的物品，如果要用该背包装如下水果，要求使背包中装的物品的价值最大，应该装下列哪些物品才能达到要求？最大价值为多少？
各水果的重量和价值如下：
苹果：5公斤，40元。
梨：2公斤，12元。
桃：1公斤，7元。
葡萄：1公斤，8元。
香蕉：6公斤，48元。
显然，我们没办法一下子就计算出哪种组合能让背包中的物品价值最大，只有通过不断地进行测试，并记录下不同物体搭配的价值，最后比较得出最大的价值。
要解决背包所装物品价值最大化的问题，可有很多种不同的方案。下面先用手工模拟一种方案。
第一步，可以从物品中任选一样装入背包。例如，选择“苹果”装入背包，则背包还剩3公斤重量的空余位置，这时，可记录装入物品的价值及总价值在如下表格中。
第二步，从剩余物品中再选一种，并判断该物品的重量是否超过背包的剩余重量，若未超过，可装入背包，并累加该物品的价值。例如，选择“梨”装入背包，将其重量、价值等记入以下表格中。
第三步，重复第二步操作，从水果中选择“桃”装入背包，将其重量、价值等记入以下表格中。
第四步，当背包已无法装下新的物品时，记下这次试装时背包所装物品的总价值。
接下来，从背包中拿出最后装入的物品，然后选择其他未装入背包的物品进行测试。例如，从上表中将“桃”拿出，重新将“葡萄”装入背包，将其重量、价值等记入以下表格中。
可以看出，背包中装入“葡萄”比“梨”的总价值要高。这时，就将目前的最高价值记录下来。
接着，再从背包中取出最后装入的“葡萄”，试着装入“香蕉”，可是背包剩余重量为1公斤，没办法装入6公斤重的“香蕉”。接着将第2步装入背包的“梨”取出，背包剩余重量为3公斤，仍然无法装入“香蕉”。继续将第1步装入背包的“苹果”取出，背包剩余重量为8公斤。这样，就可将“香蕉”装入背包了，这时背包中只有这一件物品，其重量、价值等数据如下表。
重复前面的步骤，将“梨”装入背包，记录重量、价值数据到如下表格中。
由于背包已没有剩余重量了，记录背包总价值。
重复前面的步骤，从背包中取出最后装入的物品，再测试装入其他物品。这样不断循环，直到将各种物品组合都测试完成，找出价值最高的那一次试装入即可。
看着这样重复不断试装入的步骤，是不是感觉很繁琐？在反复的装入、取出操作中，常常还会出现重复操作情况。有什么好的解决办法呢？对于重复的、相似的操作，最简单的方法就是编写程序，让计算机帮我们来完成。
11.3.2 用递归程序解决背包问题
可通过递归方法求解背包问题，递归方法解背包问题的流程如图11-4所示。
图11-4
如图11-4所示，首先将物品i试着加入背包中，接着程序判断背包中装入物品i后是否超重，如果没有超重，则继续装入下一个物品；如果已超重，则将该物品排除在本次装入方案之外，并判断排除当前物品后，所有未排除物品的价值是否小于已有最大值，若是，则不必再测试后续物品。
根据图11-4所示流程图，可编写出用递归方式解决背包问题的程序，具体代码如下：
以上程序代码比较长，不过在关键代码处都有详尽的注释。为了使程序具有一定的通用性，在主函数main()中，采用动态分配内存的方式，让用户输入物品数量、各物品的重量和价值、背包的最大重量等参数。
编译执行以上程序，按提示输入背包最大重量、物品数量及各物品的重量和价值，程序就可找出使背包中物品价值最大的组合。我们将前面例子中的数据输入，就可得到图11-5所示的计算结果。
图11-5
11.3.3 用穷举法解决背包问题
对于背包问题，也可用穷举法来解决。将可装入背包的物品通过不同的组合，试算其重量是否超过限制重量，若该组合未超过限制重量，则累加该方案中各物品的价值，得到一个总价值，再用该总价值和已有方案的最高价值进行比较，若该方案的物品价值更大，则保存该方案。
通过穷举将所有可能的组合都测试过之后，得到的就是最优的方案。
接下来就需要考虑用什么方法来得到由不同物品组成方案的组合。最简单的是：对于n个物品使用n层循环，这样就可以得到各种不同的组合。但是，对于背包问题，其物品的数量是不确定的。
对于每个物品，在生成的组合中有两种可能：一是加入背包，一是排除在背包之外。对于这种由多个物品组成，每个物品有两种可能的情况，可以使用二进制数来进行模拟。对于n个物品，就可用n位二进制数来进行模拟，当某位为1时，表示对应物品加入背包，为0时，表示不将该物品加入背包。例如，对于前面例子中的5种水果，就可用5个二进制位来表示某一种装入方案。图11-6表示一种方案，其中第1、4、5位为1，表示将第1、4、5种水果装入背包，而将第2、3种水果不装入背包。
图11-6
有了这种方案之后，接下来是二进制的表示问题。为了简化程序，可使用字符数组来保存二进制数据，一个数组元素只保存一位二进制数，也就是说，一个字符数组元素只保存0或1这两个数值之一，这样就可方便地运算。
使用二进制来穷举所有组合，首先将表示二进制数的数组全部清0，然后向该数组的低位元素逐步进行加1操作，当每一个数组元素都为1时，就表示穷举了所有可能。
根据以上分析，编写用穷举法进行背包问题求解的程序，具体实现代码如下：
编译执行以上程序，可看到与用递归法求解背包问题的程序界面完全相同，输入相同的参数（包括背包最大重量、物品数量及各物品的重量和价值等）后，程序就可找出使背包中物品价值最大的组合。如果输入图11-5所示参数，得到的结果也与图11-5相同。