前置知识

【算法】动态规划专题③ ——二维DP python

01背包问题是经典的动态规划问题之一，适用于解决在有限容量的背包中选择物品以最大化总价值的问题。每个物品只能选择一次（即“01”代表选或不选）

引入模板

01背包问题 https://www.acwing.com/problem/content/description/2/

有 $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

输出样例：

8

• 1

思路：

定义：dp[$i$][$j$]:前$i$件物品，总体积不超过$j$的最大价值

对于第i个物品，有两种选择：

1. 不选该物品：dp[i][j] = dp[i-1][j]
2. 选该物品：前提是当前背包容量足够装下该物品，即j >= w[i]，此时dp[i][j] = dp[i-1][j-w[i]] + v[i]
   因此，状态转移方程为：
   dp[i][j] = max(dp[i-1][j], dp[i-1][j - weight[i]] + value[i])

初始条件

• 当没有物品可选时，所有dp[0][j] = 0
• 当背包容量为0时，所有dp[i][0] = 0

代码如下：

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 - 1][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

滚动数组

在转移方程中，第i行的更新，仅和第i-1行有关系，因此可以使用滚动数组。
空间复杂度从O(n*v)优化为O(2*v)

code:

n, v = map(int, input().split())
dp = [[0] * (v + 1) for _ in range(2)]
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 % 2][j] = max(dp[(i - 1) % 2][j], dp[(i - 1) % 2][j - wi] + vi)
        else:
            dp[i % 2][j] = dp[(i - 1) % 2][j]
print(dp[n % 2][v])

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

再进一步优化为一维的O(v)：

code：

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(v, wi - 1, -1):
        dp[j] = max(dp[j], dp[j - wi] + vi)
print(dp[v])

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

实战演练

[NOIP 2005 普及组] 采药

题目描述

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是辰辰，你能完成这个任务吗？

输入格式

第一行有 $2$ 个整数 $T$（$1\le T\le 1000$）和 $M$（$1\le M\le 100$），用一个空格隔开，$T$ 代表总共能够用来采药的时间，$M$ 代表山洞里的草药的数目。

接下来的 $M$ 行每行包括两个在 $1$ 到 $100$ 之间（包括 $1$ 和 $100$）的整数，分别表示采摘某株草药的时间和这株草药的价值。

输出格式

输出在规定的时间内可以采到的草药的最大总价值。

样例输入

70 3
71 100
69 1
1 2

• 1
• 2
• 3
• 4

样例输出

3

• 1

【数据范围】

• 对于 $30\%$ 的数据，$M\le 10$；
• 对于全部的数据，$M\le 100$。

【题目来源】

NOIP 2005 普及组第三题

一道01背包的模板题，轻松AC

code：

t, m = map(int, input().split())
dp = [[0] * (t + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
    ti, wi = map(int, input().split())
    for j in range(1, t + 1):
        if j - ti < 0:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - ti] + wi)
print(dp[m][t])

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

滚动数组优化：

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

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

总结

01背包问题是一个典型的动态规划问题，通过定义合适的状态和状态转移方程，可以有效地解决问题。使用滚动数组优化后的算法可以大大减少空间复杂度。
理解和掌握这一类问题的解法，有助于解决更多类似的组合优化问题。

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