Python 刷题笔记：背包问题

刷动态规划的第二天，有些自闭，刚靠着大魔王的歌缓过来了。关于动态规划，我还处于看题解时哦哦哦、看题目时？？？的阶段，所以整理的点不深。除了昨天推给大家的链接，今天也是发现了一位刷题大牛的宝藏，不仅动态规划，各类算法都做了整理、引导，属实 respect ！

动态规划专题https://labuladong.gitbook.io/algo/dong-tai-gui-hua-xi-lie/dong-tai-gui-hua-xiang-jie-jin-jie

关于动态规划，我现阶段的理解是在穷举的过程中找到可以复用的求值过程，或者说找到当前要求的值与已经求好值之间的关系，建立所谓的“状态转移方程”。具体的讲解我等之后理解加深有机会再展开，刷题阶段效率为主，今天记录经典的背包题目。

题目

「0-1背包问题描述」

现在有一个可装载重量为 W 的背包和 N 个物品，每个物品有重量和价值两个属性。其中第 i 个物品的重量为 wt[i-1]，价值为 val[i-1]，现在让你用这个背包装物品，最多能装的价值是多少？

例如：W = 10, N = 5wt = [2, 2, 6, 5, 4]val = [6, 3, 5, 4, 6]
返回 15，因为可以装 [2,2,4] 重量的物品，价值分别 [6,3,6]

题目中 0-1 指的是背包装物品时，要么装整个物品、要么不装，不能只装取部分。

题目分析

因为背包有重量限制，所以当我们遍历物品时，无法确定物品是否被装入背包，就更难以找到装某一物品时与之前状态的关联。动态规划会强调“状态”，通过自定义的一维或二维数组为我们将物品装入背包这个行为定义成状态的变化，从而找到与上一次装物品之间的关联。

动态规划英文 dynamic programming，所以定义相关的状态数组多用 dp, 本题目中就是通过定义二维数组、在 Python 中即嵌套列表来实现。

背包问题中，用 dp [ i ] [ j ] 表示在物品列表中的前 i 件物品操作完、此时背包容量为 j 的状态下，背包所能装的最大价值，恰好对应了题目所求，求容量为 W 的背包、 N 个物品所实现最大价值即 dp [ N ] [ W ] 对应的值。

为何要定义这么一个奇怪的状态呢？就是为了找寻装物品时不同状态间的关系，从而建立状态转移方程。在装第 i 件物品时，对应题目中的重量和价值列表，该物品重量为 wt[i-1]、价值为 val[i-1]。

在操作这第 i 件物品之前，背包状态处于 dp [ i-1 ] [ j ] ，物品 -1、容量不变。进行到第 i 件了，要么装、要么不装就这两种选择：装的话，新的状态要在之前的价值上添加新物品的价值；不装的话，那么新状态与之前状态的价值是相等的。这便是背包问题状态转移关键所在。有种建立递归关系的意思，所以要找到初始状态值，在 i = 0 或 j = 0 时，一个是 0 件物品、一个是背包容量为 0，其价值对应为 0。之后的状态值在此基础上可以不断找到得出。

代码实现

因为本题不是 LeetCode 原题，所以解法代码没有沿用 Class 那种格式，只是定义了函数：

# n 对应个数，c 对应背包容量，w 为物品重量列表，v 物品价值列表def bag_value(n,c,w,v):  # 嵌套的列表解析式生成 c x n 的二维数组、列表    dp = [[None for j in range(c+1)] for i in range(n+1)]    # 为初始状态 i=0 或 j=0 时赋值 0     for i in range(n+1):        for j in range(c+1):            if i == 0:                dp[i][j]=0            if j == 0:                dp[i][j]=0    # 仍然遍历二维数组                for i in range(1,n+1):        for j in range(1,c+1):          # 若背包容量小于要装的物品重量，那么该物品不会被装入、状态不变            if j<w[i-1]:                dp[i][j] = dp[i-1][j]            # 若有可能装该物品，取装或不装该物品状态下最大价值            else:                dp[i][j] = max(dp[i-1][j-w[i-1]]+v[i-1],dp[i-1][j])    # 最终返回 n、c 值下的 dp 价值    return dp[n][c]
n = 5c = 10w = [2, 2, 6, 5, 4]v = [6, 3, 5, 4, 6]result = bag_value(n,c,w,v)# 可以得到 result 值为 15

这里值得注意的是，在不确定是否装该物品时，对上一个状态的取值并没有取我们之前提到的 dp [ i-1 ] [ j ] 而是对这里的背包容量处理、调整至最大容量减去第 i 件物品的重量，这是为了保证装完该物品后不超出背包容量限制，而 dp 本身对背包容量是有遍历的，所以选取的是最精准的上一状态。

感想

刷题刷到动态规划，很大的感受是我这刷题实施得太晚了，早几年就好了，之前对这些概念、算法完全没有意识。现在补过，只能说好过之后来补。

同时，潜意识里就觉着动态规划很难，所以选的策略是跳出题目，看有经验大牛的整理专题，在他们的引领下熟悉这些题目的套路，先学习、掌握要点后再通过练习来提高熟练度。

今天看这类型的题目看的脑袋大，就简单记这么些吧，明儿见～