问题简介

背包问题（Knapsack Problem）是动态规划的经典应用场景，常以如下形式出现：
给定一组物品，每种物品有对应的重量和价值，在总重量不超过背包容量的前提下，选择物品使总价值最大。
💡 典型题目：leetcode_dp_problems/01_knapsack_problem

示例分析

以 LeetCode 416 题「Partition Equal Subset Sum」为例，问题可转化为背包问题模型：

  • 物品：数组中的数字
  • 容量：数组总和的一半
  • 目标：判断是否存在子集和等于容量

关键点

  • 状态定义：dp[i][j] 表示前 i 个物品是否能凑出重量 j
  • 状态转移：若 j >= nums[i]，则 dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]]
  • 空间优化：可使用一维数组 dp[j] 降低空间复杂度

动态规划解法

def can_partition(nums):
    total = sum(nums)
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True
    for num in nums:
        for j in range(target, num - 1, -1):
            dp[j] = dp[j] or dp[j - num]
    return dp[target]

📌 复杂度：时间 O(n*target)，空间 O(target)

优化方法

扩展阅读

动态规划
背包问题
LeetCode