动态规划求打家劫舍问题最优解子集

动态规划是一种解决优化问题的有效方法，其中著名的“打家劫舍”（Knapsack Problem）是一个经典的决策问题。这个问题通常涉及选择物品放入背包以达到最大价值，但每个物品都有自己的重量限制。下面是动态规划求解打家劫舍问题的基本步骤：

1. 定义状态：设dp[i][w]表示前i个物品中选择总重量不超过w的最大价值。

2. 状态转移方程：对于第i个物品，有两种选择，要么不选（取前i-1个物品的最大价值），要么选（dp[i-1][w] + 第i个物品的价值）。取则更新状态为dp[i][w] = max(dp[i-1][w], dp[i-1][w-w_i] + v_i)，其中w_i是第i个物品的重量，v_i是它的价值。

3. 边界条件：dp[w] = 0（空背包没有价值），dp[i] = v_i（如果只考虑第i个物品，背包容量为0时价值即为第i个物品本身的价值）。

4. 最终结果：dp[n][W]就是所有物品中选取部分（不超过总重量W）能获得的最大价值，n是物品总数，W是背包容量。