前置知识

【算法】动态规划专题⑤ —— 0-1背包问题 + 滚动数组优化

完全背包问题是动态规划中的一种经典问题，它与0-1背包问题相似，但有一个关键的区别：在完全背包问题中，每种物品都有无限的数量可用。也就是说，你可以选择同一种物品多次放入背包，以使背包中的总价值最大。

示例分析
假设物品重量为 (w = [2, 3])，价值为 (v = [3, 4])，容量 (C = 5)：

最优解：选取 1 个物品1（重量2，价值3）和 1 个物品2（重量3，价值4），总价值为7。

进入正题

状态定义

设 dp[i][j] 表示前 (i) 种物品，背包容量为 j 时的最大总价值。

状态转移方程的推导

核心思想：

对第 (i) 种物品，可以选择 0 次或多次，因此需要枚举所有可能的选取次数。

暴力枚举

对每种物品 (i) 和容量 (j)，假设选取 (k) 次物品 (i)，则转移方程为：

缺点：时间复杂度为 (O(n * C * kmax)，其中 kmax= C/$w_i$ ，效率极低。

优化推导（消除对 k 的显式枚举）

观察到以下递推关系：

数学证明：

假设在容量 (j) 时，最优解中包含 (m \geq 1) 个物品 (i)，则总价值为：
dp[i][j] = dp[$i$][$j$ - $w_i$] + $v_i$
这是因为在 ($j$ - $w_i$) 容量时，已经考虑了选取 (m-1) 个物品 (i) 的最优解。

因此，状态转移方程简化为：
dp[i][j] = max ( dp[i-1][j], dp[$i$][$j$ - $w_i$] + $v_i$ )

模板

完全背包问题 https://www.acwing.com/problem/content/3/

有 $N$ 种物品和一个容量是 $V$ 的背包，每种物品都有无限件可用。
第 $i$ 种物品的体积是 $v_i$，价值是 $w_i$。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
​
输入格式
​
第一行两个整数，$N，V$，用空格隔开，分别表示物品种数和背包容积。
接下来 $N$ 行，每行两个整数 $v_i,w_i$，用空格隔开，分别表示第 $i$ 种物品的体积和价值。
​
输出格式
​
输出一个整数，表示最大价值。
​
数据范围
​
$0<N,V\le 1000$
$0<v_i,w_i\le 1000$
​
输入样例

4 5
1 2
2 4
3 4
4 5

• 1
• 2
• 3
• 4
• 5

输出样例：

10

• 1

code：

n, v = map(int, input().split())
dp = [[0] * (v + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    wi, vi = map(int, input().split())
    for j in range(1, v + 1):
        if j - wi >= 0:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - wi] + vi)
        else:
            dp[i][j] = dp[i - 1][j]
print(dp[n][v])

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10

滚动数组优化：

n, v = map(int, input().split())
dp = [0] * (v + 1)
for i in range(1, n + 1):
    wi, vi = map(int, input().split())
    for j in range(wi, v + 1):
        dp[j] = max(dp[j], dp[j - wi] + vi)
print(dp[v])

• 1
• 2
• 3
• 4
• 5
• 6
• 7

不了解 滚动数组优化 的可点此进入

END
如果有更多问题或需要进一步的帮助，可以在评论区留言讨论哦！
如果喜欢的话，请给博主点个关注 谢谢