背包问题——01背包问题
文章目录
通俗易懂的 0-1 背包问题讲解视频：带你学透0-1背包问题！| 关于背包问题，你不清楚的地方，这里都讲了！| 动态规划经典问题 | 数据结构与算法
题目来自洛谷题单背包问题
[NOIP2005 普及组] 采药
题目描述
辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是辰辰，你能完成这个任务吗？
输入格式
第一行有 $2$ 个整数 $T$（$1 \le T \le 1000$）和 $M$（$1 \le M \le 100$），用一个空格隔开，$T$ 代表总共能够用来采药的时间，$M$ 代表山洞里的草药的数目。
接下来的 $M$ 行每行包括两个在 $1$ 到 $100$ 之间（包括 $1$ 和 $100$）的整数，分别表示采摘某株草药的时间和这株草药的价值。
输出格式
输出在规定的时间内可以采到的草药的最大总价值。
样例 #1
样例输入 #1
170 3
271 100
369 1
41 2
样例输出 #1
13
提示
【数据范围】
- 对于 $30%$ 的数据，$M \le 10$；
- 对于全部的数据，$M \le 100$。
【题目来源】
NOIP 2005 普及组第三题
题解
使用二维数组：
1def main():
2 T, M = map(int, input().split(" "))
3 t, m = [0], [0]
4 for _ in range(M):
5 tn, mn = map(int, input().split(" "))
6 t.append(tn)
7 m.append(mn)
8
9 dp = [[0 for _ in range(T + 1)] for _ in range(M + 1)]
10 for i in range(1, M + 1):
11 for j in range(1, T + 1):
12 if t[i] > j:
13 dp[i][j] = dp[i - 1][j]
14 else:
15 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - t[i]] + m[i])
16 print(dp[-1][-1])
17
18
19if __name__ == "__main__":
20 main()
使用一维滚动数组：
1def main():
2 T, M = map(int, input().split(" "))
3 t, m = [0], [0]
4 for _ in range(M):
5 tn, mn = map(int, input().split(" "))
6 t.append(tn)
7 m.append(mn)
8
9 dp = [0 for _ in range(T + 1)]
10 for i in range(1, M + 1):
11 for j in reversed(range(t[i], T + 1)):
12 dp[j] = max(dp[j], dp[j - t[i]] + m[i])
13 print(dp[-1])
14
15
16if __name__ == "__main__":
17 main()
[NOIP2001 普及组] 装箱问题
题目描述
有一个箱子容量为 $V$，同时有 $n$ 个物品，每个物品有一个体积。
现在从 $n$ 个物品中，任取若干个装入箱内（也可以不取），使箱子的剩余空间最小。输出这个最小值。
输入格式
第一行共一个整数 $V$，表示箱子容量。
第二行共一个整数 $n$，表示物品总数。
接下来 $n$ 行，每行有一个正整数，表示第 $i$ 个物品的体积。
输出格式
- 共一行一个整数，表示箱子最小剩余空间。
样例 #1
样例输入 #1
124
26
38
43
512
67
79
87
样例输出 #1
10
提示
对于 $100%$ 数据，满足 $0<n \le 30$，$1 \le V \le 20000$。
【题目来源】
NOIP 2001 普及组第四题
题解
1def main():
2 V = int(input())
3 n = int(input())
4 v = [0]
5 for _ in range(n):
6 v.append(int(input()))
7
8 dp = [[0 for _ in range(V + 1)] for _ in range(n + 1)]
9 for i in range(1, n + 1):
10 for j in range(1, V + 1):
11 if v[i] > j:
12 dp[i][j] = dp[i - 1][j]
13 else:
14 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + v[i])
15 print(V - dp[-1][-1])
16
17
18if __name__ == "__main__":
19 main()
小A点菜
题目背景
uim 神犇拿到了 uoi 的 ra（镭牌）后，立刻拉着基友小 A 到了一家……餐馆，很低端的那种。
uim 指着墙上的价目表（太低级了没有菜单），说：“随便点”。
题目描述
不过 uim 由于买了一些书，口袋里只剩 $M$ 元 $(M \le 10000)$。
餐馆虽低端，但是菜品种类不少，有 $N$ 种 $(N \le 100)$，第 $i$ 种卖 $a_i$ 元 $(a_i \le 1000)$。由于是很低端的餐馆，所以每种菜只有一份。
小 A 奉行“不把钱吃光不罢休”的原则，所以他点单一定刚好把 uim 身上所有钱花完。他想知道有多少种点菜方法。
由于小 A 肚子太饿，所以最多只能等待 $1$ 秒。
输入格式
第一行是两个数字，表示 $N$ 和 $M$。
第二行起 $N$ 个正数 $a_i$（可以有相同的数字，每个数字均在 $1000$ 以内）。
输出格式
一个正整数，表示点菜方案数，保证答案的范围在 int 之内。
样例 #1
样例输入 #1
14 4
21 1 2 2
样例输出 #1
13
提示
2020.8.29，增添一组 hack 数据 by @yummy
题解
1def main():
2 N, M = map(int, input().split(" "))
3 a = [0] + list(map(int, input().split(" ")))
4
5 dp = [[0 for _ in range(M + 1)] for _ in range(N + 1)]
6 for i in range(1, N + 1):
7 for j in range(1, M + 1):
8 if j == a[i]:
9 dp[i][j] = dp[i - 1][j] + 1
10 elif j < a[i]:
11 dp[i][j] = dp[i - 1][j]
12 else:
13 dp[i][j] = dp[i - 1][j] + dp[i - 1][j - a[i]]
14 print(dp[-1][-1])
15
16
17if __name__ == "__main__":
18 main()
[NOIP2006 普及组] 开心的金明
题目描述
金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过 $N$ 元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的 $N$ 元。于是，他把每件物品规定了一个重要度，分为 $5$ 等：用整数 $1-5$ 表示，第 $5$ 等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过 $N$ 元（可以等于 $N$ 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。
设第$j$件物品的价格为 $v_j$，重要度为 $w_j$，共选中了 $k$ 件物品，编号依次为 $j_1,j_2,…,j_k$，则所求的总和为：
$$v_{j_1} \times w_{j_1}+v_{j_2} \times w_{j_2} …+v_{j_k} \times w_{j_k}$$
请你帮助金明设计一个满足要求的购物单。
输入格式
第一行，为 $2$ 个正整数，用一个空格隔开：$n,m$（$n<30000,m<25$）其中 $n$ 表示总钱数，$m$ 为希望购买物品的个数。
从第 $2$ 行到第 $m+1$ 行，第 $j$ 行给出了编号为 $j-1$ 的物品的基本数据，每行有 $2$ 个非负整数 $v,p$（其中 $v$ 表示该物品的价格 $(v \le 10000)$，$p$ 表示该物品的重要度（$1\le p\le5$）。
输出格式
$1$ 个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（$<100000000$）。
样例 #1
样例输入 #1
11000 5
2800 2
3400 5
4300 5
5400 3
6200 2
样例输出 #1
13900
提示
NOIP 2006 普及组 第二题
题解
1def main():
2 n, m = map(int, input().split(" "))
3 v, w = [0], [0]
4 for _ in range(m):
5 vi, wi = map(int, input().split(" "))
6 v.append(vi)
7 w.append(wi)
8
9 dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
10 for i in range(m + 1):
11 for j in range(n + 1):
12 if j < v[i]:
13 dp[i][j] = dp[i - 1][j]
14 else:
15 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + v[i] * w[i])
16 print(dp[-1][-1])
17
18
19if __name__ == "__main__":
20 main()
不开心的金明
题目描述
金明今天很不开心，家里购置的二手房就要领钥匙了，房里并没有一间他自己专用的很宽敞的房间。更让他不高兴的是，妈妈昨天对他说：“你需要购买哪些物品，怎么布置，你说了不算（有很大的限制），而且不超过 $W$ 元钱。”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的 $W$ 元。于是，他把每件物品规定了一个重要度整数 $p_i$ 表示。他还从因特网上查到了每件物品的价格 $v_i$（都是整数元）。
妈妈看到购物单后进行了审查，要求购物单上所有的物品价格的极差（最贵的减去最便宜的）不超过 $3$（当然金明至今不知道为什么会这样）。他希望在不超过 $W$ 元（可以等于 $W$ 元）的前提下，使购买的重要度总和 $\sum p_i$ 的最大。
请你帮助金明设计一个满足要求的购物单，你只需要告诉我们重要度的最大的和。
输入格式
输入的第 $1$ 行，为两个正整数，用一个空格隔开：
$n,W$（其中 $W$ 表示总钱数，$n$ 为希望购买物品的个数。）
从第 $2$ 行到第 $n+1$ 行，第 $j$ 行给出了编号为 $j-1$ 的物品的基本数据，每行有 $2$ 个非负整数 $v$ $p$（其中 $v$ 表示该物品的价格，$p$ 表示该物品的重要度）
输出格式
输出只有一个正整数，为不超过总钱数的物品的重要度的总和的最大值。
样例 #1
样例输入 #1
15 10
22 800
35 400
45 300
53 400
62 200
样例输出 #1
11600
提示
$1 \le N \le 100$。
$1 \le W \le 10^9$。
$1 \le v_i \le 10^9$。
对所有的 $i=1,2,3,…,N$，$\min(v_i) \le v_i \le \min(v_i)+3$。
$1 \le p_i \le 10^7$。
题解
这道题依然是一个 0-1 背包问题，和前一题的区别在于，这道题给出的背包容量（即金额限制）太大了，可能有 $10^9$ 之多，依照常规二位数组或者一维滚动数组做法必定会导致部分测试点 TLE 或 MLE。
但是经过观察题目条件我们知道，所有物品价格的极差不超过 $3$，我们不妨将所有物品的价格同时减去输入中给出的最小价格，这样所有的价格都可以以 $1$ $2$ $3$ $4$ 来表示，以此缩小 dp 数组。
在这种情况下，每购买一件物品的实际价格就相当于处理后的价格加上最低价格，那么购买 $n$ 件物品的实际价格就相当于处理后的价格加上 $n$ 倍最低价格。
因此，定义动态规划数组 dp[i][j][k] 表示在前 i 种物品种，总钱数（处理后）为 j，已购买了 k 件物品时的最大重要度。
此时 vmin * k + j 表示实际金额，而状态转移方程为 dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - v[i]][k - 1] + p[i]);。
1import java.util.Scanner;
2import java.util.Arrays;
3
4public class Main {
5 public static void main(String[] args) {
6 Scanner scanner = new Scanner(System.in);
7 int N = scanner.nextInt();
8 int W = scanner.nextInt();
9
10 int[] v = new int[N + 1];
11 int[] p = new int[N + 1];
12 for (int i = 1; i <= N; ++i) {
13 v[i] = scanner.nextInt();
14 p[i] = scanner.nextInt();
15 }
16 scanner.close();
17
18 int vmin = Arrays.stream(v, 1, N + 1).min().getAsInt();
19 int vsum = 0;
20 for (int i = 1; i <= N; ++i) {
21 v[i] -= vmin;
22 vsum += v[i];
23 }
24
25 int[][][] dp = new int[N + 1][vsum + 1][N + 1];
26 for (int i = 1; i <= N; ++i) {
27 for (int j = 0; j <= vsum; ++j) { // j 从 0 开始计数，因为处理后的价格为 0 1 2 3
28 for (int k = 1; k <= i; ++k) {
29 if (W >= vmin * k + j && j >= v[i]) {
30 dp[i][j][k] = Math.max(dp[i - 1][j][k], dp[i - 1][j - v[i]][k - 1] + p[i]);
31 } else {
32 dp[i][j][k] = dp[i - 1][j][k];
33 }
34 }
35 }
36 }
37
38 int res = 0;
39 for (int j = 0; j <= vsum; ++j) { // 这里的 j 也从 0 开始计数
40 for (int k = 1; k <= N; ++k) {
41 res = Math.max(dp[N][j][k], res);
42 }
43 }
44 System.out.println(res);
45 }
46}