背包问题——完全背包问题
文章目录
完全背包问题讲解视频：新手向 再冲完全背包两种解法 二维数组 滚动数组
题目来自洛谷题单背包问题
疯狂的采药
题目背景
此题为纪念 LiYuxiang 而生。
题目描述
LiYuxiang 是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同种类的草药，采每一种都需要一些时间，每一种也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是 LiYuxiang，你能完成这个任务吗？
此题和原题的不同点：
$1$. 每种草药可以无限制地疯狂采摘。
$2$. 药的种类眼花缭乱，采药时间好长好长啊！师傅等得菊花都谢了！
输入格式
输入第一行有两个整数，分别代表总共能够用来采药的时间 $t$ 和代表山洞里的草药的数目 $m$。
第 $2$ 到第 $(m + 1)$ 行，每行两个整数，第 $(i + 1)$ 行的整数 $a_i, b_i$ 分别表示采摘第 $i$ 种草药的时间和该草药的价值。
输出格式
输出一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。
样例 #1
样例输入 #1
170 3
271 100
369 1
41 2
样例输出 #1
1140
提示
数据规模与约定
- 对于 $30%$ 的数据，保证 $m \le 10^3$ 。
- 对于 $100%$ 的数据，保证 $1 \leq m \le 10^4$，$1 \leq t \leq 10^7$，且 $1 \leq m \times t \leq 10^7$，$1 \leq a_i, b_i \leq 10^4$。
题解
完全背包模板题，用 Python 写的话，不管是用二维数组还是一维滚动数组都会 MLE，所以使用 Java。
另外这道题的数据范围比较大，dp 数组使用 long 类型。
1import java.util.Scanner;
2
3public class Main {
4 public static void main(String[] args) {
5 Scanner scanner = new Scanner(System.in);
6 int t = scanner.nextInt();
7 int m = scanner.nextInt();
8 int[] a = new int[m + 1];
9 int[] b = new int[m + 1];
10 for (int i = 1; i <= m; i++) {
11 a[i] = scanner.nextInt();
12 b[i] = scanner.nextInt();
13 }
14 scanner.close();
15
16 long[] dp = new long[t + 1];
17 for (int i = 1; i <= m; i++) {
18 for (int j = a[i]; j <= t; j++) {
19 dp[j] = Math.max(dp[j], dp[j - a[i]] + b[i]);
20 }
21 }
22 System.out.println(dp[t]);
23 }
24}
[USACO3.1] 总分 Score Inflation
题目背景
选手在我们 USACO 的竞赛中的得分越多我们越高兴。
我们试着设计我们的竞赛以便人们能尽可能的多得分,这需要你的帮助。
题目描述
我们可以从几个种类中选取竞赛的题目，这里的一个“种类”是指一个竞赛题目的集合，解决集合中的题目需要相同多的时间并且能得到相同的分数。
你的任务是写一个程序来告诉 USACO 的职员,应该从每一个种类中选取多少题目，使得解决题目的总耗时在竞赛规定的时间里并且总分最大。
输入格式
输入的第一行是用空格隔开的两个整数，分别代表竞赛时间 $m$ 和题目类 $n$。
第 $2$ 到第 $(n + 1)$ 行，每行两个用空格隔开的整数，第 $(i + 1)$ 行的整数 $p_i, t_i$ 分别代表解决第 $i$ 类题得到的分数和需要花费的时间。
既然是某一类题目，那么这一类题目可以重复选择。
输出格式
输出一行一个整数，代表最大的总分。
样例 #1
样例输入 #1
1300 4
2100 60
3250 120
4120 100
535 20
样例输出 #1
1605
提示
数据规模与约定
对于 $100%$ 的数据，保证 $1 \leq n, m \leq 10^4$，$1 \leq p_i, t_i \leq 10^4$。
题解
这道题的提交记录里，没有人用 Python 还可以 AC 的。
1import java.util.Scanner;
2
3public class Main {
4 public static void main(String[] args) {
5 Scanner scanner = new Scanner(System.in);
6 int m = scanner.nextInt();
7 int n = scanner.nextInt();
8 int[] p = new int[m + 1];
9 int[] t = new int[m + 1];
10 for (int i = 1; i <= n; i++) {
11 p[i] = scanner.nextInt();
12 t[i] = scanner.nextInt();
13 }
14 scanner.close();
15
16 int[] dp = new int[m + 1];
17 for (int i = 1; i <= n; i++) {
18 for (int j = t[i]; j <= m; j++) {
19 dp[j] = Math.max(dp[j], dp[j - t[i]] + p[i]);
20 }
21 }
22 System.out.println(dp[m]);
23 }
24}
投资的最大效益
题目背景
约翰先生获得了一大笔遗产，他暂时还用不上这一笔钱，他决定进行投资以获得更大的效益。银行工作人员向他提供了多种债券，每一种债券都能在固定的投资后，提供稳定的年利息。当然，每一种债券的投资额是不同的，一般来说，投资越大，收益也越大，而且，每一年还可以根据资金总额的增加，更换收益更大的债券。
题目描述
例如：有如下两种不同的债券：
- 投资额 $$4000$，年利息 $$400$；
- 投资额 $$3000$，年利息 $$250$。
初始时，有 $$10000$ 的总资产，可以投资两份债券 1 债券，一年获得 $$800$ 的利息；而投资一份债券 1 和两份债券 2，一年可获得 $$900$ 的利息，两年后，可获得 $$1800$ 的利息；而所有的资产达到 $$11800$，然后将卖掉一份债券 2，换购债券 1，年利息可达到 $$1050$；第三年后，总资产达到 $$12850$，可以购买三份债券 1，年利息可达到 $$1200$，第四年后，总资产可达到 $$14050$。
现给定若干种债券、最初的总资产，帮助约翰先生计算，经过 $n$ 年的投资，总资产的最大值。
输入格式
第一行为三个正整数 $s, n, d$，分别表示最初的总资产、年数和债券的种类。
接下来 $d$ 行，每行表示一种债券，两个正整数 $a, b$ 分别表示债券的投资额和年利息。
输出格式
仅一个整数，表示 $n$ 年后的最大总资产。
样例 #1
样例输入 #1
110000 4 2
24000 400
33000 250
样例输出 #1
114050
提示
对于 $100 %$ 的数据，$1 \le s \le {10}^6$，$2 \le n \le 40$，$1 \le d \le 10$，$1 \le a \le {10}^4$，且 $a$ 是 $1000$ 的倍数，$b$ 不超过 $a$ 的 $10%$。
题解
这道题的背包容量范围比较大，如果直接声明一个大数组必然导致 MLE。题目中说所有的 a 都可以被 1000 整除，因此可以通过将数据中所有金额都除以 1000 来优化。
1def main():
2 s, n, d = map(int, input().split(" "))
3 a, b = [0], [0]
4 for _ in range(d):
5 ai, bi = map(int, input().split(" "))
6 a.append(ai // 1000)
7 b.append(bi + ai)
8
9 for _ in range(n):
10 s = dp(s, d, a, b)
11 print(s)
12
13
14def dp(s, d, a, b):
15 s0 = s - (s // 1000) * 1000
16 s //= 1000
17 dparr = [0 for _ in range(s + 1)]
18 for i in range(d + 1):
19 for j in range(a[i], s + 1):
20 dparr[j] = max(dparr[j], dparr[j - a[i]] + b[i])
21 return dparr[-1] + s0
22
23
24if __name__ == "__main__":
25 main()
[USACO08NOV] Buying Hay S
题目描述
Farmer John is running out of supplies and needs to purchase H (1 <= H <= 50,000) pounds of hay for his cows.
He knows N (1 <= N <= 100) hay suppliers conveniently numbered 1..N. Supplier i sells packages that contain P_i (1 <= P_i <= 5,000) pounds of hay at a cost of C_i (1 <= C_i <= 5,000) dollars. Each supplier has an unlimited number of packages available, and the packages must be bought whole.
Help FJ by finding the minimum cost necessary to purchase at least H pounds of hay.
约翰的干草库存已经告罄，他打算为奶牛们采购 $H(1 \leq H \leq 50000)$ 磅干草。
他知道 $N(1 \leq N\leq 100)$ 个干草公司，现在用 $1$ 到 $N$ 给它们编号。第 $i$ 公司卖的干草包重量为 $P_i (1 \leq P_i \leq 5,000)$ 磅，需要的开销为 $C_i (1 \leq C_i \leq 5,000)$ 美元。每个干草公司的货源都十分充足， 可以卖出无限多的干草包。
帮助约翰找到最小的开销来满足需要，即采购到至少 $H$ 磅干草。
输入格式
* Line 1: Two space-separated integers: N and H
* Lines 2..N+1: Line i+1 contains two space-separated integers: P_i and C_i
输出格式
* Line 1: A single integer representing the minimum cost FJ needs to pay to obtain at least H pounds of hay.
样例 #1
样例输入 #1
12 15
23 2
35 3
样例输出 #1
19
提示
FJ can buy three packages from the second supplier for a total cost of 9.
题解
这道题的坑在于，当购买的干草数量比 H 更大时，价格反而更便宜，而题目的要求正好是“至少 H 磅干草”而且“开销最小”。所以这道题里的数组长度不是 H + 1 而是 H + max(P) + 1。填完数组后，从 dp[H:] 中搜寻最小值。
这道题中的状态转移方程是 dp[j] = min(dp[j], dp[j - P[i]] + C[i])。但是倘若将数组初始化为 0，那么最小值一直是 0。因此需要将 dp[0] 初始化为 0 而其他位置初始化为 5e5（可能出现的最大值）。
1def main():
2 N, H = map(int, input().strip().split(" "))
3 P, C = [0], [0]
4 for _ in range(N):
5 Pi, Ci = map(int, input().strip().split(" "))
6 P.append(Pi)
7 C.append(Ci)
8
9 max_pound = H + max(P)
10 # 先全部赋成最大值，但是 dp[0] 必须是 0，不然第一个 dp[j - P[i]] + C[i] 也会无比大
11 dp = [0] + [5e5 for _ in range(1, max_pound + 1)]
12 for i in range(1, N + 1):
13 for j in range(P[i], max_pound + 1):
14 dp[j] = min(dp[j], dp[j - P[i]] + C[i])
15 print(min(dp[H:]))
16
17
18if __name__ == "__main__":
19 main()