动态规划用于求解01背包问题的最优解

文章目录

• 【模板】01背包
• 分割等和子集
• 目标和
• 最后一块石头的重量 II

我是紫色

【模板】01背包

模板

思路
第一问

• 状态定义：在动态规划问题中，dp[i][j]被用来表示从前i个物品中选择若干个，在总体积不超过j的情况下所能达到的最大价值。

  • 状态转移逻辑：根据第i个物品是否被选取来决定当前状态的计算方式。
    • 若第i个物品未被选取，则有dp[i][j]=dp[i−1][j]
    • 若第i个物品被选取，则需满足剩余容量足以支持该物品的选择条件（即j−v[i]>=0），此时的状态值为dp[i−1][j−v[i]]+w[i]
    • 综上所述，在所有可能的选择方案中取最大值的结果即为当前状态的状态转移方程：

      dp[i][j] = \max(dp[i - 1][j], dp[i - 1][j - v_i] + w_i)

• 初始设置操作开始：

• 当首行列值设为零时（即采用编号为零的物品进行取用）