# 运筹学教学 | 动态规划例题分析(一）

30 3

win

``` 1/*
2    example input: 30 3
3    example output: win
4*/
5#include<bits/stdc++.h>
6using namespace std;
7int n, k;// n个火柴，每次取1..k个
8int *dp;
9int main(){
10    scanf("%d %d", &n, &k);
11    dp = new int[n + 1];
12    for (int i = 1; i <= n; i ++) dp[i] = 0;
13
14    dp[1] = 1;// 先手一根必输
15
16    for (int i = 1; i <= n; i += k + 1) dp[i] = 1;// 每隔k+1个出现一次必输态
17
18    if (dp[n]) printf("lose\n");
19    else printf("win\n");
20}```

9 4 6

6 0

6 4

9 1

0 1

1 0

1 4

5 0

5 4

9 0

0 0

10

```  1/*
29 4 6
3数据保证有解
4*/
5#include<bits/stdc++.h>
6using namespace std;
7
8int **dp; // dp[i][j] 表示第一个杯子是i，第二个杯子是j的时候的最小步数
9int m, n; // 表示两个杯子的容量。
10int T; // T 为目标函数值
11struct arr{
12    int x, y;
13};
14
15arr make_arr(int x, int y){
16    arr tmp;
17    tmp.x = x;
18    tmp.y = y;
19    return tmp;
20}
21
22bool operator <(const arr &a, const arr &b){
23    return (a.x < b.x || (a.x == b.x && a.y < b.y));
24}
25
26bool operator ==(const arr &a, const arr &b){
27    return (a.x == b.x && a.y == b.y);
28}
29
30map<arr, arr> solution;
31
32void dfs(int x, int y){
33    //达到目标值
34    if (x == T || y == T) return;
35
36    //倒空B
37    if (dp[x][0] < 0){
38        dp[x][0] = dp[x][y] + 1;
39        dfs(x, 0);
40        solution[make_arr(x, 0)] = make_arr(x, y);
41    }
42
43    //加满A
44    if (dp[m][y] < 0){
45        dp[m][y] = dp[x][y] + 1;
46        dfs(m, y);
47        solution[make_arr(m, y)] = make_arr(x, y);
48    }
49
50    //加满B
51    if (dp[x][n] < 0){
52        dp[x][n] = dp[x][y] + 1;
53        dfs(x, n);
54        solution[make_arr(x, n)] = make_arr(x, y);
55    }
56
57    //倒空A
58    if (dp[0][y] < 0) {
59        dp[0][y] = dp[x][y] + 1;
60        dfs(0, y);
61        solution[make_arr(0, y)] = make_arr(x, y);
62    }
63
64    //A加入B
65    if (x + y <= n && dp[0][x + y] < 0){
66        dp[0][x + y] = dp[x][y] + 1;
67        dfs(0, x + y);
68        solution[make_arr(0, x + y)] = make_arr(x, y);
69    }
70
71    if (x + y > n && dp[x - n + y][n] < 0){
72        dp[x - n + y][n] = dp[x][y] + 1;
73        dfs(x - n + y, n);
74        solution[make_arr(x - n + y, n)] = make_arr(x, y);
75    }
76
77    //B加入A
78    if (x + y <= m && dp[x + y][0] < 0){
79        dp[x + y][0] = dp[x][y] + 1;
80        dfs(x + y, 0);
81        solution[make_arr(x + y, 0)] = make_arr(x, y);
82    }
83
84    if (x + y > m && dp[m][x + y - m] < 0){
85        dp[m][x + y - m] = dp[x][y] + 1;
86        dfs(m, x + y - m);
87        solution[make_arr(m, x + y - m)] = make_arr(x, y);//记录路径，上同
88    }
89
90}
91
92
93int main(){
94    scanf("%d %d %d", &m, &n, &T);
95
96    dp = new int*[m + 1];
97    for (int i = 0; i <= m; i ++){
98        dp[i] = new int[n + 1];
99        for (int j = 0; j <= n; j ++){
100            dp[i][j] = -1;//开始不能达到
101        }
102    }
103    dp[0][0] = 0;//初始化边界条件
104    dfs(0, 0);// dp过程
105    int id_x, id_y;
106    int ans = 0x7fffffff, ans1 = ans, ans2 = ans;
107    if (T > m) {// 如果目标值大于第二个杯子，那么最优解在第一个杯子里面
108        for (int i = 0; i <= m; i ++)
109            if (dp[i][T] > 0 && ans1 > dp[i][T] + (int)(i > 0)) {
110                ans1 = dp[i][T] + (i > 0);
111                id_x = i;
112            }
113    }
114    else if (T > n){//如果目标值大于第一个杯子，那么最优解在第二个杯子里面
115        for (int i = 0; i <= n; i ++)
116            if (dp[T][i] > 0 && ans2 > dp[T][i] + (int)(i > 0)) {
117                ans2 = dp[T][i] + (i > 0);
118                id_y = i;
119            }
120    }
121    else{
122        for (int i = 0; i <= m; i ++)
123            if (dp[i][T] > 0 && ans1 > dp[i][T] + (int)(i > 0)) {
124                ans1 = dp[i][T] + (i > 0);
125                id_x = i;
126            }
127        for (int i = 0; i <= n; i ++)
128            if (dp[T][i] > 0 && ans2 > dp[T][i] + (int)(i > 0)) {
129                ans2 = dp[T][i] + (i > 0);
130                id_y = i;
131            }
132    }//两个杯子都有可能
133    if (ans1 < ans2){
134        ans = ans1 + 1;//初始00也算一步。。
135        printf("%d %d\n", 0, T);
136        arr tmp = make_arr(id_x, T);
137        while (tmp.x || tmp.y){
138            printf("%d %d\n", tmp.x, tmp.y);
139            tmp = solution[tmp];
140        }
141        printf("%d %d\n", tmp.x, tmp.y);
142    }else{
143        ans = ans2 + 1;
144        printf("%d %d\n", T, 0);
145        arr tmp = make_arr(T, id_y);
146        while (tmp.x || tmp.y){
147            printf("%d %d\n", tmp.x, tmp.y);
148            tmp = solution[tmp];
149        }
150        printf("%d %d\n", tmp.x, tmp.y);//回溯找解
151    }
152    printf("%d\n", ans);
153}```

10 5

1 0

3 1 2 3

3 4 5 6

2 7 8

1 9

550 900 770

680 790 1050

580 760 660

510 700 830

610 790

540 940

790 270

1030

1390

2870

0 1 4 7 9

```  1/*
2sample input:
310 5
41 0
53 1 2 3
63 4 5 6
72 7 8
81 9
9550 900 770
10680 790 1050
11580 760 660
12510 700 830
13610 790
14540 940
15790 270
161030
171390
18*/
19
20#include<bits/stdc++.h>
21using namespace std;
22#define INF 0x3f3f3f3f
23
24int **dp;// dp方程
25int **graph;// 从至表
26int N, T;// 城市数量以及阶段数量
27int *fa;// 记录上一个访问。
28typedef vector<int> List;
29List *Nodes;// node[i]表示i的下层节点
30
31void print(int x){
32    if (x == fa[x]){
33        printf("%d ", x);
34        return;
35    }else{
36        print(fa[x]);
37        printf("%d ", x);
38    }
39}
40
41int main(){
42    scanf("%d %d", &N, &T);
43
44    dp = new int*[T];
45    for (int i = 0; i < T; i ++){
46        dp[i] = new int[N];
47        for (int j = 0; j < N; j ++) dp[i][j] = INF;
48    }//初始化
49
50    Nodes = new List[T];
51    int m, x;
52    for (int i = 0; i < T; i ++){
53        scanf("%d", &m);
54        Nodes[i].clear();
55        for (int j = 0; j < m; j ++){
56            scanf("%d", &x);
57            Nodes[i].push_back(x);
58        }
59    }// 读入每一层包含的节点编号
60
61    graph = new int*[N];
62    fa = new int[N];
63    for (int i = 0; i < N; i ++){
64        graph[i] = new int[N];
65        fa[i] = i;//初始化前驱节点，方便记录路径
66        for (int j = 0; j < N; j ++){
67            graph[i][j] = INF;
68        }
69    }// 初始化输入输出
70
71    for (int i = 0; i < T - 1; i ++){
72        int sz_1 = Nodes[i].size(), sz_2 = Nodes[i + 1].size();
73        for (int j = 0; j < sz_1; j ++){
74            for (int k = 0; k < sz_2; k ++){
75                scanf("%d", &graph[Nodes[i][j]][Nodes[i + 1][k]]);
76            }
77        }
78    }// 读入每一层结点与下层节点之间的距离
79
80    for (int i = 0; i < Nodes[0].size(); i ++) dp[0][Nodes[0][i]] = 0;// 初始化边界，到达出发点花费为0
81    for (int i = 1; i < T; i ++){
82        int sz_1 = Nodes[i].size(), sz_2 = Nodes[i - 1].size();
83        for (int j = 0; j < sz_1; j ++){
84            int x = Nodes[i][j];
85            for (int k = 0; k < sz_2; k ++){
86                int y = Nodes[i - 1][k];
87                //dp[i][x] = min(dp[i][x], dp[i - 1][y] + graph[y][x]);
88                if (dp[i][x] > dp[i - 1][y] + graph[y][x]){
89                    dp[i][x] = dp[i - 1][y] + graph[y][x];// 更新dp方程
90                    fa[x] = y;// 记录路径
91                }
92            }
93        }
94    }
95    for (int i = 0; i < Nodes[T - 1].size(); i ++){
96        printf("%d\n", dp[T - 1][Nodes[T - 1][i]]);
97        int x = Nodes[T - 1][i];
98        print(x);
99        printf("\n");
100    }// 输出路径以及结果
101}```

0 条评论