0-1背包问题(Knapsack Problem)-动态规划方法（递归和迭代)

前言

背包0-1问题属于典型的求最大/最小子集问题范畴，它不像rod-cutting或matrix-chain-multiplication等问题，求解过程是按照单位等增或单位递减，0-1背包问题属于在集合范围内的某一个值，而且这些值大概率不是连续值。

问题描述

假定有N件物品，每件物品具有特定的价值value[i]和重量weight[i](1<=i<=N)；现给定一个背包，此背包有总重量的限制W，求解这个包装载的物品具有最大价值和。

为什么把此问题称作0-1问题呢？ 因为每件物品都有两种状态，如果没有选择，可以称作为状态0，如果选择，那么可以标记为状态1.

用具体的示例进行说明，为了阐述方便，我们规定物品有3件，背包最大承重W<=50kg, 表格勾画出问题。

Item # No.ValueWeight
16010
210020
312030

如果我们用穷举法，可以得到8类不同的组合，对于每个不同组合，可以计算其总价值和总重量，最后选择满足总重量要求的最大价值。

其中灰色代表左边的物件未放入背包，绿色代表物件已经背包，需要考虑其重量和价值。我们以C3选择为例说明，C3选择了物件1和物件2放入背包，那么我们就可以求出背包内所放置物品的价值总和 与 重量总和**(160,30)**。
sum_value=∑(60+100)=160sum\_value=∑(60+100)=160 sum_value=∑(60+100)=160

sum_weight=∑(10+20)=30sum\_weight=∑(10+20)=30 sum_weight=∑(10+20)=30

通过观察，可以发现C7包含的价值最大,为280；但同时如果考虑背包所能最大的承重 W<=50,那么显然C7不符合求解要求。再继续观察，我们发现 C6组合**(220,50)**既满足背包最大承重要求，也满足价值最大的要求，那么C6就是我们最终的选择，也即选择物件2和物件3放入背包，可以获得最大的价值。

针对三件物品，我们可以采用穷举法罗列所有可能的选项，如果物品件数较多，假设有10件物品，就需要罗列1024次才可能求出最终的解；假定有N件物品，如果采用穷举法，我们需要进行2^N 罗列才能求出解，显然这样效率很低，在N较大时候，程序运行效率很低，甚至无法求解。

按照《算法导论》的模板，仍然采用CRCC模式对此问题进行分析。

a) 表征最优解的结构(Characterize the structure of optimal solution)

要计算背包所能装载的最大价值，同时满足背包的承重要求。如果我们走一个极端，如果背包可以无限承重，那么此问题就转换为所有物品价值简单求和的问题，因为物品的价值总为正，物品越多，那么其放入背包后的价值就越大，在此极端情况下，我们不需要用到任何优化，运用动态规划意义不大。

所以我们最优解的结构一定包含两个参数，参数之一为物件的数量n(1<=n<=N)，另外一个参为背包的最大承重W，作为约束条件物件的重量总和必须≤W.

如果采用朴素的函数语言，我们可以将表征最优解的结构抽象为函数结构：
f(n,w)=max{f(n−1,w),f(n−1,w−weight[n])+value[n]}orf(n−1,w)f(n,w)=max\{f(n-1,w),f(n-1,w-weight[n])+value[n]\} or f(n-1,w) f(n,w)=max{f(n−1,w),f(n−1,w−weight[n])+value[n]}orf(n−1,w)
其中f(n-1,w)表示我们舍弃第n个物件，相当于直接跳过第n个物件，直接操作第n-1个物件，由于舍弃第n个物件，此选择的价值为0，也就是f(n-1,w)+0.

其中f(n-1,w-weight[n])+value[n](如果是C语言，要替换weight[n]\为weight[n-1]，value[n]\为value[n-1])表示，把第n件物品的价值包含在内，然后往前回退，选择包含第n件物品后果：

  1. 所能承受的总重从w减少到w-weight[n]，直观理解就是因为放入第n件物品，当前包的允许装载重量降低
  2. 选择第n件物品，那么其函数值需要追加value[n]在内

当背包允许容纳第n件物品的时候，我们需要在放入(1)和不放入 (0)之间作出选择，取二者之间的最大值；

当背包不允许容纳第n件物品的时候，我们需要直接跳过第n件物品，采用前(n-1)件中的物品装入的价值；

值得一提的是, 函数f(n,w)中的n并非表示背包中装了n件物品，而是对n件物品完成放入/不放入选择后的评估后得到结果，背包的总装入件数<=n。

由于没件物品的重量是离散分布，函数f(n,w)中的w是离散量，并不是连续量，这和rod-cutting或matrix-chain-multiplication等问题连续分布不一样，如果我们设定w的范围(0=<w<=W)，很多时候，只有和重量匹配的位置上，f(n,w)的求值才有具体含义。

b）递归定义最优解的值(Recursively define the value of the optimal solution)

实际上上我们在上述分析中，已经完成了对最优解的值的定义， 在此省略。

c) 计算最优解的值(Compute the value of the optimal solution)

首先我们采用递归定义求解最优解的值，而且在递归过程中，我们先不采用memo记忆数组，这样做的目的是为了更好理解程序的执行流程。对于f(n,w)的递归终结条件为，当n=0的时候，也就是没有任何物件的时候，无论背包允许放入重量为多少，那么f(n,w)的值一定为0；如果背包允许放入的重量为0或为负数，那么f(n,w)的值也为0；这两种状态下递归需要返回的值为0。

假设我们现在有三件物品和一个背包，我们已经了解其基本信息如下：

  • N=3, 物品件数

  • W=50, 背包所能承受的最大重量

  • value[N] = {60,100,120}

  • weight[N] = {10, 20, 30}

通过递归，我们形成如下的递归树：

其中每个节点(n,weight)，n代表目前已经对前n个物品做出选择，weight代表剩余重量（还可以容纳的重量，也即剩余容纳重量)。

其中黄色highlight部分未通过选择对背包增加的价值，价值0代表未把此物件放入背包；蓝色highlight部分为节点通过比较大小获取的结果（选择的结果），由于重量为离散值，而且当物件数目比较小的情况下，子树的重复性不算是非常明显，本例子中我们看到仅有(0,20）数值重复。

采用C语言，递归程序如下（无memo).

P1. 定义头文件,knapsack_recursive.h

/** * @file knapsack_recursive.h * @author your name (you@domain.com) * @brief* @version 0.1 * @date 2023-02-27 ** @copyright Copyright (c) 2023 **/#ifndef KNAPSACK_RECURSIVE_H#define KNAPSACK_RECURSIVE_H#include #include #include //Total of items that can be placed into the bag#define N 3#define W 50/** * @brief Use recursive method to find the maximum value from n items * within no more than weight capacity ** @param weight weight array * @param valuevalue array* @param nnumber of items * @param weight_capacity weight capacity for the bag * @return int -maximum value */int knapsack_resursive(int *weight, int *value,int n,int weight_capacity);/** * @brief look for the bigger value from m,n ** @param m Value of m * @param n Value of n * @return int Bigger value from both of them */int max(int m,int n);#endif

P2. 函数实现,knapsack_recursive.c, 其中knapsack_resursive输入物件数量和背包总的容纳重量，进行top-down方式的递归实现。

/** * @file knapsack_recursive.c * @author your name (you@domain.com) * @brief* @version 0.1 * @date 2023-02-27 ** @copyright Copyright (c) 2023 **/#ifndef KNAPSACK_RECURSIVE_C#define KNAPSACK_RECURSIVE_C#include "knapsack_recursive.h"int knapsack_resursive(int *weight, int *value, int n, int weight_capacity){int incl_item;//include the current itemint excl_item;//exclude the current itemint max_value;if(n==0 || weight_capacity==0){return 0;}if (weight[n - 1] > weight_capacity)// int value[N] = {60,100,120}; N=3; W=50// int weight[N] = {10, 20, 30};{max_value = knapsack_resursive(weight, value, n - 1, weight_capacity);}else{excl_item=knapsack_resursive(weight,value,n-1,weight_capacity);incl_item=knapsack_resursive(weight,value,n-1,weight_capacity-weight[n-1])+value[n-1];max_value =max(excl_item,incl_item);} return max_value;}int max(int m, int n){return (m>n" />:n);}#endif

P3. 主函数测试

/** * @file knapsack_recursive_main.c * @author your name (you@domain.com) * @brief* @version 0.1 * @date 2023-02-27 ** @copyright Copyright (c) 2023 **/#ifndef KNAPSACK_RECURSIVE_MAIN_C#define KNAPSACK_RECURSIVE_MAIN_C#include "knapsack_recursive.c"int main(void){int value[N] = {60,100,120};int weight[N] = {10,20,30};int n;int w;n=N;w=W;int max_value;max_value=knapsack_resursive(weight,value,n,w);printf("The maximum value is %d\n",max_value);getchar();return EXIT_SUCCESS;}#endif

对于递归函数的memo方法，请读者自行完成。

接下来让我们回到bottom-up的迭代模式，很多人在做动态规划的时候，喜欢迭代模式，因为迭代模式看起来优雅，并且代码实现很多时候比较简洁，但是bottom-up的挑战之一是定义dp数组，而且需要初始化某些前置的dp数组值，这两点都给bottom-up模式带来很大的挑战，就让我们来迎接挑战吧！

首先我们定义dp数组，我们有N件物品，可以把N件物品作为第一个维度；同时我们还有允许装入背包的总重量限制W；这两个值在过程中都是动态变化的，所以自然而然我们考虑到dp应该选取二维数组,dp[i][j]。

我们需要给dp[i][j]赋予bottom-up的含义，其含义为：对前面的i件物品做出选择判断，确保其总重不超过j的重量，j可以理解为还允许装入的重量。

dp数组的维度确认后，还需要确认dp数组之间的关联，用专业术语来讲，也就是所谓的状态方程的确认。

如果第i件物品允许装入背包，也即背包剩余的允许重量j>weight[i-1], weight[i-1]代表第i件物品的实际重量。在这种条件下，我们有两类选择：

  • 选择装入,dp[i-1][j]

  • 选择不装入,dp[i-1][j-weight[i-1]]+value[i-1]

此时dp[i][j]=max{dp[i-1][j], dp[i-1][j-weight[i-1]]+value[i-1]}。

开始遇到knapsack的时候，一直思考如何和j-1建立关联，实质上是走入了思维误区。除非有重量等于1的背包，否则j-1就是一类不存在的子问题，因为j代表背包剩余的允许重量，这时候就需要采用j-weight[i-1]为下标，代表装入第i件物品后，那么已经装入第i-1件的背包的最大允许重量减少至j-weigh[i-1]，这个值也是i-1物件允许装入重量的上限。它相当于跨域多列，进行dp之间的关联。

由于背包的重量限制，第i件物品不允许装入背包，那么这时候的操作就比较简单，直接d[i][j]=dp[i-1][j]即可。

初始化dp[i][j]也相对而言比较简单，我们在i=0或j=0的条件下，赋值dp[0][j]=0或dp[i][0]=0，dp[0][j]表示没有物品，背包的允许重量无论多少，其转入物品的总价值都为0；dp[i][0]表示背包已经达到设计的重量，没有任何可以装入重量的余量（0表示允许剩余装入量）。

基于上面分析，我们来呈上bottom-up的代码。

/** * @file knapsack_bottomup.c * @author your name (you@domain.com) * @brief* @version 0.1 * @date 2023-02-27 ** @copyright Copyright (c) 2023 **/#ifndef KNAPSACK_BOTTOMUP_C#define KNAPSACK_BOTTOMUP_C#include "knapsack_bottomup.h"void knapsack_bottomup(int *weight, int *value, int n, int capacity, int dp[N + 1][W + 1]){int i; //items indicatorint j; //weight indicatorint k;//Initialize//if there is no items inside, then it is worth zero valuefor(k=0;k<=W;k++){dp[0][k]=0;}// Initialize// if the column contains zero weight, then it is worth zero valuefor(k=0;k<=N;k++){dp[k][0]=0;}for(i=1;i<=N;i++){for(j=1;j<=W;j++){if(j<weight[i-1]) //it can't fit the single weight of ith{dp[i][j]=dp[i-1][j];}else{dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i-1]]+value[i-1]);}}}}int max(int m, int n){return (m>n?m:n);}#endif

对于bottom-up程序，我们可以对dp数组进行空间上的优化，可以采用dp[2][W+1]形式的数组，或者采用dp[W+1]数组，自右向左进行操作即可。

总结：

通过0-1背包问题的学习，更深刻认识到动态规划中0-1选择问题，以及由于重量的离散而导致与上一个问题关联的离散性。这个问题采用dp[i][j]更加直观和方便程序，当然也可以优化成dp[2][W+1]或dp[W+1]的数组进行迭代使用。

参考文献：

1.《Introduction to algorithm, 4ed》

  1. 动态规划法（四）0-1背包问题（0-1 Knapsack Problem）_山阴少年的博客-CSDN博客_0-1 knapsack