当前位置：首页 > article >正文

【算法】动态规划专题⑨ —— 二维费用背包问题 python

article 2025/2/9 5:25:22

前置知识

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

进入正题

二维费用背包问题

方法思路
二维费用背包问题在传统背包问题的基础上增加了第二个维度的限制（如重量）。
每个物品具有两种费用（体积和重量），背包在这两个维度上都有容量限制。
我们需要在不超过两种容量限制的前提下，选择物品使得总价值最大。

我们需要定义一个三维数组dp[i][j][k]，表示从前i个物品中选择，重量不超过j、第二种费用不超过k时可以获得的最大价值。
不过，为了节省空间，通常可以将三维数组简化为二维数组，因为当前状态只依赖于前一个状态。

关键步骤：

状态定义：使用二维数组 dp[j][k] 表示在体积为 j 和重量为 k 时的最大价值。
状态转移：对于每个物品，逆序遍历体积和重量，确保每个物品只被选取一次。

该方法通过动态规划高效地处理了二维费用限制，确保在合理的时间复杂度内找到最优解。时间复杂度为 O(N*V*W)

好了，实际运用的时候到了

实战演练

二维费用的背包问题 https://www.acwing.com/problem/content/8/

题目描述

有 $N$ 件物品和一个容量是 $V$ 的背包，背包能承受的最大重量是 $M$ 。
每件物品只能用一次。体积是 $v_i$ ，重量是 $m_i$ ，价值是 $w_i$ 。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，总重量不超过背包可承受的最大重量，且价值总和最大。

输入格式

第一行三个整数， $N, V, M$ ，用空格隔开，分别表示物品件数、背包容积和背包可承受的最大重量。

接下来有 $N$ 行，每行三个整数 $v_i, m_i, w_i$ ，用空格隔开，分别表示第 $i$ 件物品的体积、重量和价值。

输出格式

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

数据范围

$\lt N \le 1000$
$\lt V, M \le 100$
$\lt v_i, m_i \le 100$
$\lt w_i \le 1000$

输入样例

输出样例：

code：

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