前言
练习智能车招新题时,遇到很多超过时间的,以前做题都是暴力的,不追求算法,能对就行
做到一些稍微有点难度的 就发现以前一直听说的动态规划,听名字以前一直不敢学习
之前遇到要dp的都是问GPT,自己看代码一知半解就过了,现在还是觉得应该系统学习一下的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
|
/*
一组研究人员正在设计一个测试猴子IQ的实验。他们把香蕉吊在屋顶上，同时给猴子提供了砖块。如果猴子够聪明，它会把砖块一个个叠起来做成一个塔，然后爬上去拿到自己喜爱的食物。
研究人员有n种不同的砖块，而且每种砖块都是取之不尽的。每种砖块都是长方体，第i种砖块的大小是（xi，yi，zi）。砖块能够翻转，可以将任意两边当作底面，剩下的那边作为高。
他们想确定用砖块搭成的最高塔，能否帮助猴子够着屋顶。问题是，在叠塔过程中，要放的那块砖，其底面两条边都要小于下面那块砖的两条边，这是为了留个空间给猴子踩脚。
例如，底面相同尺寸的砖块不能相叠。
现给定砖块，请计算猴子能够叠塔的最大高度。
输入格式
输入包含多组测试数据。每组输入的第一行是一个整数n，表示砖块的种类数。n的最大值是30。
接着n行，每行输入三个整数xi，yi和zi。
当n=0时，输入结束。
输出格式
对于每组输入，输出一行：测试例编号case（从1开始编号），塔能够达到的最大高度height。
输出格式为：“Case case: maximum height = height”。
样例
输入数据 1
1
10 20 30
2
6 8 10
5 5 5
7
1 1 1
2 2 2
3 3 3
4 4 4
5 5 5
6 6 6
7 7 7
5
31 41 59
26 53 58
97 93 23
84 62 64
33 83 27
0
输出数据 1
Case 1: maximum height = 40
Case 2: maximum height = 21
Case 3: maximum height = 28
Case 4: maximum height = 342
*/
int dp[MAX_N+1][2*MAX_SUM+1]; // 动态规划表，用于记录最小差值
int sum_r = 0, sum_f = 0;
// 返回两个数的最小值
int min(int a, int b) {
return a < b ? a : b;
}
// 返回两个数的最大值
int max(int a, int b) {
return a > b ? a : b;
}
// 解决糖果分配问题
void solve(int n, int m, int *ri, int *fi) {
memset(dp, -1, sizeof(dp)); // 初始化动态规划表
dp[0][OFFSET] = 0; // 没有糖果时，差值为0
for (int i = 0; i < n; i++) {
sum_r += ri[i];
sum_f += fi[i];
for (int j = m; j > 0; j--) {
for (int k = -MAX_SUM; k <= MAX_SUM; k++) {
int adjusted_k = k + OFFSET; // 将负数索引转换为正数
int new_diff = k + (ri[i] - fi[i]);
if (dp[j-1][adjusted_k] != -1 && abs(new_diff) <= MAX_SUM) {
dp[j][new_diff + OFFSET] = max(dp[j][new_diff + OFFSET], dp[j-1][adjusted_k] + ri[i] + fi[i]);
}
}
}
}
int min_diff = 1000000;
int max_sum = 0;
for (int k = -MAX_SUM; k <= MAX_SUM; k++) {
if (dp[m][k + OFFSET] != -1) {
int diff = abs(k);
if (diff < min_diff) {
min_diff = diff;
max_sum = dp[m][k + OFFSET];
} else if (diff == min_diff) {
max_sum = max(max_sum, dp[m][k + OFFSET]);
}
}
}
printf("%d\n", min_diff);
printf("%d\n", max_sum);
}
int main() {
int n, m;
scanf("%d %d", &n, &m);
int ri[n], fi[n];
for (int i = 0; i < n; i++) {
scanf("%d %d", &ri[i], &fi[i]);
}
solve(n, m, ri, fi);
return 0;
}
|
01背包
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| 一、01背包问题
有 N 件物品和一个容量是 V的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤1000
0<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
8
|
根据B站上的教程 我认为以下视频可以入门:
【自制】01背包问题算法动画讲解
带你学透0-1背包问题！| 关于背包问题，你不清楚的地方，这里都讲了！| 动态规划
对于01背包要注意的就是:
1
| dp[i][j]=dp[i-1][j]>dp[i-1][j-vi[i-1]]+wi[i-1]?dp[i-1][j]:dp[i-1][j-vi[i-1]]+wi[i-1];
|
01背包经典代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| int knapsack01(int weights[], int values[], int n, int W) {
int dp[W + 1];
for (int i = 0; i <= W; i++) {
dp[i] = 0;
}
for (int i = 0; i < n; i++) {
for (int w = W; w >= weights[i]; w--) {
dp[w] = (dp[w] > dp[w - weights[i]] + values[i]) ? dp[w] : (dp[w - weights[i]] + values[i]);
}
}
return dp[W];
}
|
