528
个编辑
更改
无编辑摘要
有 ''num'' 个物品和容量为 ''weight'' 的背包，每个物品都有自己的体积 ''w'' 和价值 ''v''，求拿哪些物品可以使得背包所装下物品的总价值最大。如果限定每种物品只能选择 0 或 1 个，则为 0-1 背包问题；如果不限定每种物品的数量，则为无界背包问题或完全背包问题。
有 ''num'' 个物品和容量为 ''weight'' 的背包，每个物品都有自己的体积 ''w'' 和价值 ''v''，求拿哪些物品可以使得背包所装下物品的总价值最大。如果限定每种物品只能选择 0 或 1 个，则为 0-1 背包问题；如果不限定每种物品的数量，则为无界背包问题或完全背包问题。
状态矩阵使用二维数组，<code>dp[i][j]</code> 表示前 i 件物品体积不超过 j 的情况下能达到的最大价值。
=== 0-1 背包 ===
=== 0-1 背包 ===
每件物品只能选择拿或不拿。状态转移方程为
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v) (if j >= w)
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v) (if j >= w)
dp[i-1][j] (if j < w)
dp[i-1][j] (if j < w)
可以进行空间压缩，使用一维的 <code>dp</code> 数组，内层需要逆向遍历。
<syntaxhighlight lang=python>
<syntaxhighlight lang=python>
def knapsack(weights: list[int], values: list[int], int weight_goal):
def knapsack(weights: list[int], values: list[int], int weight_goal):
=== 完全背包 ===
=== 完全背包 ===
一个物品可以拿多次。状态转移方程为
dp[i][j] = max(dp[i-1][j], dp[i][j-w] + v) (if j >= w)
dp[i-1][j] (if j < w)
和 0-1 背包相比，仅仅是把状态转移方程中的第二个 i-1 变成了 i。在进行空间压缩时，内层正向遍历
<syntaxhighlight lang=python>
def knapsack(weights: list[int], values: list[int], int weight_goal):
dp = [0 for _ in range(w + 1)]
for w in weights:
for j in range(w, weight_goal + 1):
dp[j] = max(dp[j], dp[j-w] + values[i])
return dp[weight_goal]
</syntaxhighlight>
== 相关题目 ==
== 相关题目 ==
dp[i][n0][n1] = dp[i - 1][n0][n1]
dp[i][n0][n1] = dp[i - 1][n0][n1]
return dp[slen][m][n]
return dp[slen][m][n]
</syntaxhighlight>
=== 完全背包：[https://leetcode.com/problems/coin-change/ LeetCode 322. Coin Change] ===
<syntaxhighlight lang=python>
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [float('inf') for _ in range(amount + 1)]
dp[0] = 0
for c in coins:
for am in range(c, amount + 1):
dp[am] = min(dp[am], dp[am - c] + 1)
return -1 if dp[amount] == float('inf') else dp[amount]
</syntaxhighlight>
</syntaxhighlight>