【算法】动态规划专题⑥ —— 完全背包问题 python

前置知识

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

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

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

容量 (j)	2	3	4	5
初始化	0	0	0	0
物品1（w=2）	3	3	6	6
物品2（w=3）	3	4	6	7

最优解：选取 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$ 种物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

$\lt N, V \le 1000$
$\lt v_i, w_i \le 1000$

输入样例

输出样例：

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])

滚动数组优化：

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])