本文主要是介绍备战蓝桥杯Day35 - 动态规划 - 01背包问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
问题描述
隐含前提：
1.物体是不可分的，要么装，要么不装，不能只装一部分。
2.物体顶多使用一次。
动态规划思路
我在b站上看的闫氏dp分析大法的视频，他对dp问题做了总结归纳。
从集合的角度分析dp问题。求出有限集中的最值 / 个数。
分析内容主要包括两部分：
1.状态表示（化零为整）：将一些有相似特征的元素化成一个子集，用某一个状态表示。
1.1 明确集合分类
1.2 明确题目中要找的属性（最大值 / 最小值 / 个数）
2.状态计算（化整为零）：将数据划分为不同的子集。（依据：寻找最后一个不同点）
2.1 数据不重复
2.2 数据不遗漏
分析01背包问题
1.集合：
所有只考虑前 i 个物品，且总体积不超过 j 的选法的集合
2.属性：
集合中每个方案的最大值
3. 状态计算：
第一种：所有不选第 i 个物品的集合。
所以要从第1个到第 i - 1 中进行选择，且总体积不超过 j 。 dp[ i ][ j ] = dp[ i-1 ][ j ]
第二种：所以选了第 i 个物品的集合
我们已经选了第 i 个， 所以前 i-1个物品我们要选出最大值，且 前 i-1个物品的总体积为 j - vi。
dp[ i ][ j ] = dp[i-1][j - vi] + wi
这两种情况我们要取最大值。
所以最后状态计算表达式为：
dp[ i ][ j ] = max(dp[ i - 1][ j ], dp[i-1][j - vi] + wi)
代码实现
def knapsack_01(N, V, volumes, values): # 初始化 dp 数组，dp[i][j] 表示考虑前 i 件物品，在容量为 j 的背包中能够得到的最大价值 dp = [[0 for _ in range(V + 1)] for _ in range(N + 1)] # 动态规划过程 for i in range(1, N + 1): for j in range(1, V + 1): # 如果第 i 件物品的体积大于当前背包容量 j，则不能装入 if volumes[i - 1] > j: dp[i][j] = dp[i - 1][j] else: # 否则考虑放入和不放入两种情况，取较大者 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - volumes[i - 1]] + values[i - 1]) # 返回最大价值，即所有物品考虑在内，背包容量为 V 的最大价值 return dp[N][V] # 读取输入
N, V = map(int, input().split())
volumes = []
values = []
for _ in range(N): v, w = map(int, input().split()) volumes.append(v) values.append(w) # 输出最大价值
print(knapsack_01(N, V, volumes, values))读取输入这样写就很妙，学会了。一点一点的进步吧！
这篇关于备战蓝桥杯Day35 - 动态规划 - 01背包问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
