背包问题——多维背包问题
文章目录
题目来自洛谷题单背包问题 和 NEFU OJ
QWQ 和 QAQ (reprise)
之前遇见过的 QWQ 和 QAQ 这道题，实际上也可以按照三维完全背包的方式来解（时间复杂度和空间复杂度更高，但是可以 AC）。
题解
1#define _CRT_SECURE_NO_WARNINGS
2
3#include <cstdio>
4#include <cstring>
5#include <algorithm>
6
7using namespace std;
8
9int t, a[4] = { 0 }, b[4] = { 0 }, c[4] = { 0 }, d[4] = { 0 }, dp[205][205][205], i, j, k, l;
10
11int main() {
12 scanf("%d", &t);
13
14 while (t--) {
15 for (i = 1; i <= 4; i++) {
16 scanf("%d%d%d", &a[i % 4], & b[i % 4], &c[i % 4]);
17 }
18 scanf("%d%d%d", &d[1], &d[2], &d[3]);
19
20 memset(dp, 0, sizeof(dp));
21 for (i = 1; i <= 3; i++) {
22 for (j = a[i]; j <= a[0]; j++) {
23 for (k = b[i]; k <= b[0]; k++) {
24 for (l = c[i]; l <= c[0]; l++) {
25 dp[j][k][l] = max(dp[j][k][l], dp[j - a[i]][k - b[i]][l - c[i]] + d[i]);
26 }
27 }
28 }
29 }
30
31 printf("%d\n", dp[a[0]][b[0]][c[0]]);
32 }
33}
榨取kkksc03
题目描述
洛谷 2 的团队功能是其他任何 OJ 和工具难以达到的。借助洛谷强大的服务器资源，任何学校都可以在洛谷上零成本的搭建 OJ 并高效率的完成训练计划。
为什么说是搭建 OJ 呢？为什么高效呢？
因为，你可以上传私有题目，团队外别人是无法看到的。我们还能帮你们评测！
你可以创建作业，给组员布置任务，查看组员的完成情况，还可以点评任意一份代码！
你可以创建比赛！既可以是 OI 赛制还可以是 ICPC 赛制！既可以是团队内部的私有比赛，也可以公开赛，甚至可以指定谁可以参加比赛。这样，搞“x 校联赛”最合适不过了。洛谷凭借这个功能，希望能够提供公开及私有比赛的另外一个平台。
值得说明的是，本次比赛就是采用团队私有题目+邀请比赛的机制。
洛谷的运营组决定，如果一名 OIer 向他的教练推荐洛谷，并能够成功的使用（成功使用的定义是：该团队有 $20$ 个或以上的成员，上传 $10$ 道以上的私有题目，布置过一次作业并成功举办过一次公开比赛），那么他可以浪费掉 kkksc03 的一些时间的同时消耗掉 kkksc03 的一些金钱以满足自己的一个愿望。
kkksc03 的时间和金钱是有限的，所以他很难满足所有同学的愿望。所以他想知道在自己的能力范围内，最多可以完成多少同学的愿望？
输入格式
第一行三个整数 $n,M,T$，表示一共有 $n$（$1 \le n \le 100$）个愿望， kkksc03 的手上还剩 $M$（$0 \le M \le 200$）元，他的暑假有 $T$（$0 \le T \le 200$）分钟时间。
第 $2$~$n+1$ 行 $m_{i}$ , $t_{i}$ 表示第 $i$ 个愿望所需要的金钱和时间。
输出格式
一行，一个数，表示 kkksc03 最多可以实现愿望的个数。
样例 #1
样例输入 #1
16 10 10
21 1
32 3
43 2
52 5
65 2
74 3
样例输出 #1
14
题解
简单的二维 0-1 背包问题，而且每种物品的价值相同（都是 1）。
1#define _CRT_SECURE_NO_WARNINGS
2
3#include <cstdio>
4#include <algorithm>
5
6using namespace std;
7
8int N, M, T, dp[205][205] = { 0 }, mi, ti, i, j, k;
9
10int main() {
11 scanf("%d%d%d", &N, &M, &T);
12 for (i = 0; i < N; i++) {
13 scanf("%d%d", &mi, &ti);
14 for (j = M; j >= mi; j--) {
15 for (k = T; k >= ti; k--) {
16 dp[j][k] = max(dp[j][k], dp[j - mi][k - ti] + 1);
17 }
18 }
19 }
20 printf("%d", dp[M][T]);
21}
甚至用 Python 都能 AC：
1def main():
2 N, M, T = map(int, input().strip().split(" "))
3 dp = [[0 for _ in range(T + 1)] for _ in range(M + 1)]
4
5 for i in range(N):
6 mi, ti = map(int, input().strip().split(" "))
7 for j in reversed(range(mi, M + 1)):
8 for k in reversed(range(ti, T + 1)):
9 dp[j][k] = max(dp[j][k], dp[j - mi][k - ti] + 1)
10 print(dp[-1][-1])
11
12
13if __name__ == "__main__":
14 main()
NASA的食物计划
题目背景
NASA（美国航空航天局）因为航天飞机的隔热瓦等其他安全技术问题一直大伤脑筋，因此在各方压力下终止了航天飞机的历史，但是此类事情会不会在以后发生，谁也无法保证。所以，在遇到这类航天问题时，也许只能让航天员出仓维修。但是过多的维修会消耗航天员大量的能量，因此 NASA 便想设计一种食品方案，使体积和承重有限的条件下多装载一些高卡路里的食物。
题目描述
航天飞机的体积有限，当然如果载过重的物品，燃料会浪费很多钱，每件食品都有各自的体积、质量以及所含卡路里。在告诉你体积和质量的最大值的情况下，请输出能达到的食品方案所含卡路里的最大值，当然每个食品只能使用一次。
输入格式
第一行 $2$ 个整数，分别代表体积最大值 $h$ 和质量最大值 $t$。
第二行 $1$ 个整数代表食品总数 $n$。
接下来 $n$ 行每行 $3$ 个数 体积 $h_i$，质量 $t_i$，所含卡路里 $k_i$。
输出格式
一个数，表示所能达到的最大卡路里（int 范围内）
样例 #1
样例输入 #1
1320 350
24
3160 40 120
480 110 240
5220 70 310
640 400 220
样例输出 #1
1550
提示
对于 $100%$ 的数据，$h,t,h_i,t_i \le 400$，$n \le 50$，$k_i \le 500$。
题解
1def main():
2 H, T = map(int, input().split(" "))
3 N = int(input())
4 dp = [[0 for _ in range(H + 1)] for _ in range(T + 1)]
5
6 for i in range(N):
7 hi, ti, ki = map(int, input().split(" "))
8 for j in range(ti, T + 1)[::-1]:
9 for k in range(hi, H + 1)[::-1]:
10 dp[j][k] = max(dp[j][k], dp[j - ti][k - hi] + ki)
11 print(dp[-1][-1])
12
13
14if __name__ == "__main__":
15 main()
[NOIP2010 提高组] 乌龟棋
题目背景
NOIP2010 提高组 T2
题目描述
小明过生日的时候，爸爸送给他一副乌龟棋当作礼物。
乌龟棋的棋盘是一行 $N$ 个格子，每个格子上一个分数（非负整数）。棋盘第 $1$ 格是唯一的起点，第 $N$ 格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。
乌龟棋中 $M$ 张爬行卡片，分成 $4$ 种不同的类型（$M$ 张卡片中不一定包含所有 $4$ 种类型的卡片，见样例），每种类型的卡片上分别标有 $1,2,3,4$ 四个数字之一，表示使用这种卡片后，乌龟棋子将向前爬行相应的格子数。游戏中，玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片，控制乌龟棋子前进相应的格子数，每张卡片只能使用一次。
游戏中，乌龟棋子自动获得起点格子的分数，并且在后续的爬行中每到达一个格子，就得到该格子相应的分数。玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的分数总和。
很明显，用不同的爬行卡片使用顺序会使得最终游戏的得分不同，小明想要找到一种卡片使用顺序使得最终游戏得分最多。
现在，告诉你棋盘上每个格子的分数和所有的爬行卡片，你能告诉小明，他最多能得到多少分吗？
输入格式
每行中两个数之间用一个空格隔开。
第 $1$ 行 $2$ 个正整数 $N,M$，分别表示棋盘格子数和爬行卡片数。
第 $2$ 行 $N$ 个非负整数，$a_1,a_2,…,a_N$，其中 $a_i$ 表示棋盘第 $i$ 个格子上的分数。
第 $3$ 行 $M$ 个整数，$b_1,b_2,…,b_M$，表示 $M$ 张爬行卡片上的数字。
输入数据保证到达终点时刚好用光 $M$ 张爬行卡片。
输出格式
一个整数，表示小明最多能得到的分数。
样例 #1
样例输入 #1
19 5
26 10 14 2 8 8 18 5 17
31 3 1 2 1
样例输出 #1
173
提示
每个测试点 1s。
小明使用爬行卡片顺序为 $1,1,3,1,2$，得到的分数为 $6+10+14+8+18+17=73$。注意，由于起点是 $1$，所以自动获得第 $1$ 格的分数 $6$。
对于 $30%$ 的数据有 $1≤N≤30,1≤M≤12$。
对于 $50%$ 的数据有 $1≤N≤120,1≤M≤50$，且 $4$ 种爬行卡片，每种卡片的张数不会超过 $20$。
对于 $100%$ 的数据有 $1≤N≤350,1≤M≤120$，且 $4$ 种爬行卡片，每种卡片的张数不会超过 $40$；$0≤a_i≤100,1≤i≤N,1≤b_i≤4,1≤i≤M$。
题解
最开始我尝试使用深搜，然后就不出意外地超时了。尝试用动态规划解决它。定义 dp[i][j][k][l] 来表示打出 i 张 $1$、j 张 $2$、k 张 $3$ 和 l 张 $4$ 时的最大得分。因为有第一个格子当保底，所以 dp[0][0][0][0] 初始化为 a[1]。
1#define _CRT_SECURE_NO_WARNINGS
2
3#include <cstdio>
4#include <algorithm>
5#include <cstring>
6
7using namespace std;
8
9int a[355], N, M, pos, i, j, k, l, c, card[5] = { 0 }, dp[45][45][45][45];
10
11int main() {
12 scanf("%d%d", &N, &M);
13 for (i = 1; i <= N; i++) {
14 scanf("%d", &a[i]);
15 }
16 for (i = 0; i < M; i++) {
17 scanf("%d", &c);
18 card[c]++;
19 }
20
21 dp[0][0][0][0] = a[1];
22 for (i = 0; i <= card[1]; i++) {
23 for (j = 0; j <= card[2]; j++) {
24 for (k = 0; k <= card[3]; k++) {
25 for (l = 0; l <= card[4]; l++) {
26 pos = 1 + i + 2 * j + 3 * k + 4 * l;
27
28 if (i > 0) {
29 dp[i][j][k][l] = max(dp[i][j][k][l], dp[i - 1][j][k][l] + a[pos]);
30 }
31 if (j > 0) {
32 dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j - 1][k][l] + a[pos]);
33 }
34 if (k > 0) {
35 dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j][k - 1][l] + a[pos]);
36 }
37 if (l > 0) {
38 dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j][k][l - 1] + a[pos]);
39 }
40 }
41 }
42 }
43 }
44 printf("%d\n", dp[card[1]][card[2]][card[3]][card[4]]);
45
46 return 0;
47}