基础算法：两步理解基础背包问题

╰+哭是因爲堅強的太久メ 2022-12-13 11:22 101阅读 0赞

动态规划问题中最为典型的问题之一就是背包问题，而0-1背包是其中最为基础的，N个物品具有各自的重量和价值，根据背包可容纳的重量W的限制，求取在此限制之下能装入的物品的最大价值，一般情况下会转化为dp的一个N\*W复杂度的问题求解，这篇文章通过简单的示例进行解释和说明。

### 目录 ###

*  背包问题
 *  问题描述
 *  状态转移方程
 *  知识点
 *   *  知识点1: 初始化
     *  知识点2: 问题拆解
 *  模拟实现
 *  总结

# 背包问题 #

背包最早可以追溯至1897年由数学家托比亚斯·丹齐格所提出的在如何满足行李不超载的情况下尽可能的向旅行箱中添加最有价值物品的的问题，也就是说如何选择最合适（价值最高）的物品于给定背包（背包能装入的重量有限制）中，这也是背包问题名称的来源，它在1978年由Merkle和Hellman提出，类似的问题在很多领域中都有应用。

# 问题描述 #

> 给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。每种物品仅有一件，可以选择放或不放，这也是基础的0-1背包的特点。

# 状态转移方程 #

> 状态转移方程：f\[i\]\[v\]=max\{ f\[i-1\]\[v\], f\[i-1\]\[v-w\[i\]\]+v\[i\] \}

说明：

*  v\[\]: 存放物品的价值
 *  w\[\]: 存放物品的重量
 *  f\[i\]\[v\]: 在背包容量为v的情况下，放入前i个物品，f\[i\]\[v\]保存的为此种情况下的最大价值

--------------------

注意：如果使用下表从0开始的数组表示的时候，在实现的时候v\[i\]可能会是v\[i-1\]，当然也可以将v\[0\]不保存内容，从v\[1\]开始即可根状态转移方程完全一致了。

# 知识点 #

使用动态规划法解决基础背包或者0-1背包问题，理解如下两个知识点是关键。觉得有点难以理解可以先结合后文实现示例进行理解。

## 知识点1: 初始化 ##

初始化内容主要如下三部分：

*  物品重量：weight\[\] 通过输入获取
 *  物品价值：value\[\] 通过输入获取
 *  dp数组：根据动态规划的基本套路，初始化dp数组，dp数组参照状态转移方程进行构建即可，可创建如下二维dp数组dp\[i\]\[j\]
    
     *  i：表示物品个数
     *  j：背包容量

> 第一个知识点集：dp数组的初始化需要注意如下事项
> 
>  *  行表示物品个数，列表示背包容量
>  *  行总数为物品个数+1，第一行表示物品为零时的dp\[0\]\[j\]的值，表示没有物品，所以初始值应为0
>  *  列总数为输入的背包容量+1，第一列表示背包容量为0的情况下的最大价值，因为背包容量为0，放不进物品，所以初始值也应为0

## 知识点2: 问题拆解 ##

> 状态转移方程：f\[i\]\[v\]=max\{ f\[i-1\]\[v\], f\[i-1\]\[v-w\[i\]\]+v\[i\] \}

问题的拆解最重要的就是上述的状态转移方程，对于对于动态规划方法不熟悉的读者可以参考如下说明进行理解，熟悉的可以直接跳过：

> 第二个知识点集：dp数组的初始化需要注意如下事项
> 
>  *  f\[i\]\[v\]为当前的求解，其值为 f\[i-1\]\[v\]和f\[i-1\]\[v-w\[i\]\]+v\[i\]中大的那个，前者表示不将序号为i的物品放入背包，后者为放入，求解即为在这二者之中择优。
>  *  f\[i-1\]\[v-w\[i\]\]+v\[i\]表示把需要为i的物品放入的时候的求解，问题拆解为v\[j\]和i-1个物品的最大价值的和，后者最大容量的可能即为v-w\[i\]，而保存前i-1个物品在最大容量为v-w\[i\]的情况下的最大价值即保存在f\[i-1\]\[v-w\[i\]\]中，这是已经拆解和解决过的问题。
>  *  能够放入或者不能放入可以通过v和v\[i\]的关系来判断，前者如果小于v\[i\]自然无论如何都放不进去，此时的值也应该为f\[i-1\]\[v\]

--------------------

# 模拟实现 #

比如此处使用C来模拟简单的背包问题，示例代码如下所示：

#include <stdio.h>
    
    #define MAX_N 100
    #define MAX_WEIGHT 10000
    
    int max(int a, int b) { 
        return a>b?a:b;
    }
    
    void knapsack(int num, int input_weight) { 
        int weight[MAX_N] = {  0 };
        int value[MAX_N] = {  0 };
        int dp[MAX_N][MAX_WEIGHT] = {  0 };
        for (int i=0; i<num; i++) { 
            scanf("%d",&weight[i]);
        }
        for (int i=0; i<num; i++) { 
            scanf("%d",&value[i]);
        }
        for (int i=0; i<input_weight+1; i++) { 
            dp[0][i] = 0;
        }
        for (int i=0; i<num+1; i++) { 
            dp[i][0] = 0;
        }
    
        for (int i=1; i<=num; i++) { 
            for (int j=1; j<=input_weight; j++) { 
                if (j < weight[i-1]) { 
                    dp[i][j] = dp[i-1][j];
                } else { 
                    dp[i][j] = max(dp[i-1][j],value[i-1]+dp[i-1][j-weight[i-1]]);
                }
            }
        }
    
        printf("%d\n",dp[num][input_weight]);
    }
    
    int main(void) { 
        int num=0, input_weight=0;
        while (scanf("N=%d, W=%d",&num, &input_weight) != EOF) { 
            knapsack(num,input_weight);
        }
    }

可以看到，代码及其简单，简单说明如下：

*  此部分代码为初始化部分的内容，前文提到过重量weight和价值value的数组是通过输入赋值，dp的首行首列根据具体意义全部设定为0，作为后续链式推导的基础。

int weight[MAX_N] = {  0 };
        int value[MAX_N] = {  0 };
        int dp[MAX_N][MAX_WEIGHT] = {  0 };
        for (int i=0; i<num; i++) { 
            scanf("%d",&weight[i]);
        }
        for (int i=0; i<num; i++) { 
            scanf("%d",&value[i]);
        }
        for (int i=0; i<input_weight+1; i++) { 
            dp[0][i] = 0;
        }
        for (int i=0; i<num+1; i++) { 
            dp[i][0] = 0;
        }

*  这是模拟的0-1背包问题解决的核心代码，可以看到两层的循环，也就是前文所提到的W\*N的时间复杂度的来源，此处i-1和状态转移方程不同的原因在于数组使用时下标从0开始，如果从1开始，可保持一致，其余内容在前文的知识点二中都进行了说明。

for (int i=1; i<=num; i++) { 
            for (int j=1; j<=input_weight; j++) { 
                if (j < weight[i-1]) { 
                    dp[i][j] = dp[i-1][j];
                } else { 
                    dp[i][j] = max(dp[i-1][j],value[i-1]+dp[i-1][j-weight[i-1]]);
                }
            }
        }

*  执行示例  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdW1pYW9jbg_size_16_color_FFFFFF_t_70_pic_center]

# 总结 #

本文对于背包问题进行了简单的解释和说明，背包问题有很多变种，可以再此基础上进行进一步的理解。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdW1pYW9jbg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/9fb7a12e5e4e44669ef742fafa3215f7.png