|
作为运筹优化领域中一种极其重要的算法，动态规划可以说是非常skr好用了，那么为了方便大家的理解，这里给出几个了几个来源于《Operations Research: Applications and Algorithm》例题以及对应例题的例程来参考。参考书以及相关资料请移步留言区！ 例题1： 问题描述 假设桌子上有n根火柴，我先手取1，2,…,k(k<> 输入数据只有一行，n和k分别表示火柴总数和每次取的最大数量。 输出数据只有一行，如果先手获胜输出win否则输出lose。 样例输入 30 3 样例输出 win 样例数据解释 先手者保证火柴数量每次都取到29，25，21，17，13，9，5，1就能够达到必胜状态。 题目分析 对于样例数据，从最终状态分析，如果最后只有一根火柴，则当时取的人一定会输。那么如果先手面对的是5根火柴，那么无论怎么取，后手都有办法使先手操作时达到只剩下1根火柴的必输状态。同理，剩下9，13，17,…,29根火柴的时候先手的人一定会输。 这样规律就很明显了，如果先手开局面对的不是必输态，那么先手只需要将当前局势调整为后手必输态那么先手就赢了。而调整的方法就是让场上的火柴数量处于p * (k+1) + 1, p = 1,2,…的状态。 所以，令dp[i]表示当前场上剩余i根火柴的时候的状态，dp[i] =1表示必输态，dp[i] = 0表示必胜态，则动态规划的转移应该是 dp[i] = dp[i - k - 1], 边界条件是dp[1] = 1, dp[2] = dp[3] = …= dp[k+1] = 0; 代码展示 1/*
2 example input: 30 3
3 example output: win
4*/
5#include
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 <>0;
13
14 dp[1] = 1;// 先手一根必输
15
16 for (int i = 1; i <>1) dp[i] = 1;// 每隔k+1个出现一次必输态
17
18 if (dp[n]) printf('lose\n');
19 else printf('win\n');
20}
例题2 问题描述 我现在有一个m-oz的杯子和一个n-oz的杯子，我妈妈要求我带回家恰好T-oz的牛奶，我应该如何实现？ 输入数据只有一行 m, n, T分别表示两个杯子的容量以及目标牛奶量（要带回家的牛奶量）。 输出数据有若干行，最后一行是一个数字p，表示最小的操作次数，前面p行表示操作路径(倒序) 样例输入 9 4 6 样例输出 6 0 6 4 9 1 0 1 1 0 1 4 5 0 5 4 9 0 0 0 10 样例数据解释 开始有一个9-oz的杯子和一个4-oz的杯子，目标是带回家6-oz的牛奶。首先倒满9oz之后把9oz倒入4oz的杯子加满，得到一个装着5oz和4oz牛奶的杯子，然后倒掉4oz的那一杯，再把5oz的那一杯倒入4oz那一杯，再倒掉，这时9oz的杯子里面有1oz牛奶，4oz的那一个杯子是空的，把那1oz的牛奶倒入4oz杯子里面，再加满9oz的杯子，最后用9oz杯子里面的牛奶倒入4oz的杯子里面，就得到了6oz的牛奶。 题目分析 要用动态规划解决这个问题，首先要划清楚状态转移，一共有6种操作，8种状态。分别是倒空A杯子，倒空B杯子，倒满A杯子，倒满B杯子，用A倒满B(两种状态，A比B多或者比B少)，用B倒满A（两种状态，A比B多或者比B少） 需要注意的是，当达到某一种状态之后，之后的状态都是通过这种状态转移过来，而对于每一个子问题，都是与原问题相似的问题，因此满足子问题的重叠性。 我们另dp[x][y]表示达到杯子A中有xoz的牛奶，B中有yoz的牛奶的状态的最小步骤，那么dp[x][y] = min(dp[i][j]) + 1, 其中i，j是所有能够推到x，y的状态。转移有了，对于边界就是初始状态下，dp[0][0] = 0. 代码展示 1/*
29 4 6
3数据保证有解
4*/
5#include
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 <><>
24}
25
26bool operator ==(const arr &a, const arr &b){
27 return (a.x == b.x && a.y == b.y);
28}
29
30map 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 <>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 <>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 <>
98 dp[i] = new int[n + 1];
99 for (int j = 0; 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 <>
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 <>
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 <>
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 <>
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 <>
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}
进入今天的最后一题了呢，想想还是有些按捺不住自己内心的激动呢！ 例题3 问题描述 小明住在纽约，但是他想开车(这个人为什么不坐飞机)去拉斯维加斯去追求金钱和名声。但是，众所周知，小明很穷，所以他每次都只能开到附近朋友的房子里面，然后休整一下, 准备第二天再出发。由于小明平日比较积德，所以他的朋友很多。他经过规划知道，第一天可以到某几个朋友(比如小红，小白)家，然后第二天从前日借宿的朋友家出发可以到另一组朋友中的一人的家中，如此重复几天，最终可以到达拉斯维加斯。 现在约定，小明一共有n-2个朋友，所以包括他家以及拉斯维加斯一共有n个点，他每天可以从k_t个朋友中选择一个到达，但是到达每一家的花费不同，请问小明如何用最省钱的方式到达拉斯维加斯。 输入数据，第一行两个整数n和m分别表示小明可以落脚的点的数量（包括自己家，朋友家，拉斯维加斯）和预算到达的天数(在自己家和拉斯维加斯都要算一天)。 接下来m-2行中的第i行的第一个数字k_i表示第i+1天可以到达的朋友家数量，后面k_i个数表示这k_i个朋友的编号。当然，接下来一行是数字1和拉斯维加斯的编号。 接下来n-1行，第i行有k_i+1个数字表示小明第i天的落脚点到第i+1天的落脚点之间的距离。 输出数据, 共有两行，第一行是一个整数，表示最小花费，第二行是路程方案，用空格隔开。 注意，数据中落脚点的编号是0..n-1并非0..n 样例输入 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 样例解释 样例数据中输入数据做出的图如下图3-1，依照这个图可以算出最小花费为2870，路径为0-1-4-7-9（图中编号为1,…,n,对应到图上要每个编号加一） 题目分析 这是一个比较简单的题目，题目中状态划分比较清楚，定义dp[i][j]表示第i阶段到达j城市的最小距离即可，很容易就能够推出动归方程dp[i][j] = min(dp[i][j], dp[i-1][k]+dis[k][j])，其中dis[k][j]表示城市k与城市j之间的距离。 代码展示 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
21using namespace std;
22#define INF 0x3f3f3f3f
23
24int **dp;// dp方程
25int **graph;// 从至表
26int N, T;// 城市数量以及阶段数量
27int *fa;// 记录上一个访问。
28typedef vectorint> 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 <>
46 dp[i] = new int[N];
47 for (int j = 0; j <>
48 }//初始化
49
50 Nodes = new List[T];
51 int m, x;
52 for (int i = 0; i <>
53 scanf('%d', &m);
54 Nodes[i].clear();
55 for (int j = 0; 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 <>
64 graph[i] = new int[N];
65 fa[i] = i;//初始化前驱节点，方便记录路径
66 for (int j = 0; j <>
67 graph[i][j] = INF;
68 }
69 }// 初始化输入输出
70
71 for (int i = 0; i <>1; i ++){
72 int sz_1 = Nodes[i].size(), sz_2 = Nodes[i + 1].size();
73 for (int j = 0; j <>
74 for (int k = 0; k <>
75 scanf('%d', &graph[Nodes[i][j]][Nodes[i + 1][k]]);
76 }
77 }
78 }// 读入每一层结点与下层节点之间的距离
79
80 for (int i = 0; i <>0].size(); i ++) dp[0][Nodes[0][i]] = 0;// 初始化边界，到达出发点花费为0
81 for (int i = 1; i <>
82 int sz_1 = Nodes[i].size(), sz_2 = Nodes[i - 1].size();
83 for (int j = 0; j <>
84 int x = Nodes[i][j];
85 for (int k = 0; 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 <>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}
【如对代码有疑问，可联系小编，可以提供有偿辅导服务】 【有偿辅导纯属个人行为，与团队无关】
|
