更改

[[Category:动态规划]]

[[Category:动态规划]]

背包问题，使用动态规划求解。

背包问题，使用动态规划求解。

有 ''num'' 个物品和容量为 ''weight'' 的背包，每个物品都有自己的体积 ''w'' 和价值 ''v''，求拿哪些物品可以使得背包所装下物品的总价值最大。如果限定每种物品只能选择 0 或 1 个，则为 0-1 背包问题；如果不限定每种物品的数量，则为无界背包问题或完全背包问题。

有 ''num'' 个物品和容量为 ''weight'' 的背包，每个物品都有自己的体积 ''w'' 和价值 ''v''，求拿哪些物品可以使得背包所装下物品的总价值最大。如果限定每种物品只能选择 0 或 1 个，则为 0-1 背包问题；如果不限定每种物品的数量，则为无界背包问题或完全背包问题。

== 0-1 背包 ==

=== 0-1 背包 ===

每件物品只能选择拿或不拿。使用二维数组，<code>dp[i][j]</code> 表示前 i 件物品体积不超过 j 的情况下能达到的最大价值。状态转移方程为

每件物品只能选择拿或不拿。使用二维数组，<code>dp[i][j]</code> 表示前 i 件物品体积不超过 j 的情况下能达到的最大价值。状态转移方程为

</syntaxhighlight>

</syntaxhighlight>

== 完全背包 ==

=== 完全背包 ===