首页 > 搜索 > 运筹学动态规划算法例题,运筹学教学|动态规划例题分析(一)

运筹学动态规划算法例题,运筹学教学|动态规划例题分析(一)

互联网 2020-10-29 01:54:02
在线算命,八字测算命理

作为运筹优化领域中一种极其重要的算法,动态规划可以说是非常skr好用了,那么为了方便大家的理解,这里给出几个了几个来源于《Operations Research: Applications and Algorithm》例题以及对应例题的例程来参考。

下面开始精彩的例题展示部分了

例题1:

问题描述

假设桌子上有n根火柴,我先手取1,2,…,k(k dp[T][i] + (int)(i > 0)) {117ans2 = dp[T][i] + (i > 0);118id_y = i;119}120}121else{122for (int i = 0; i0 && ans1 > dp[i][T] + (int)(i > 0)) {124ans1 = dp[i][T] + (i > 0);125id_x = i;126}127for (int i = 0; i0 && ans2 > dp[T][i] + (int)(i > 0)) {129ans2 = dp[T][i] + (i > 0);130id_y = i;131}132}//两个杯子都有可能 133if (ans1 < ans2){134ans = ans1 + 1;//初始00也算一步。。 135printf("%d %d\n", 0, T);136arr tmp = make_arr(id_x, T);137while (tmp.x || tmp.y){138printf("%d %d\n", tmp.x, tmp.y);139tmp = solution[tmp];140} 141printf("%d %d\n", tmp.x, tmp.y);142}else{143ans = ans2 + 1;144printf("%d %d\n", T, 0);145arr tmp = make_arr(T, id_y);146while (tmp.x || tmp.y){147printf("%d %d\n", tmp.x, tmp.y);148tmp = solution[tmp];149} 150printf("%d %d\n", tmp.x, tmp.y);//回溯找解 151}152printf("%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之间的距离。

图3-1

代码展示

1/*2sample input:310 541 053 1 2 363 4 5 672 7 881 99550 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 vector List; 29List *Nodes;// node[i]表示i的下层节点 30 31void print(int x){ 32if (x == fa[x]){ 33printf("%d ", x); 34return; 35}else{ 36print(fa[x]); 37printf("%d ", x); 38} 39} 40 41int main(){ 42scanf("%d %d", &N, &T); 43 44dp = new int*[T]; 45for (int i = 0; i < T; i ++){ 46dp[i] = new int[N]; 47for (int j = 0; j < N; j ++) dp[i][j] = INF; 48}//初始化 49 50Nodes = new List[T]; 51int m, x; 52for (int i = 0; i < T; i ++){ 53scanf("%d", &m); 54Nodes[i].clear(); 55for (int j = 0; j < m; j ++){ 56scanf("%d", &x); 57Nodes[i].push_back(x); 58} 59}// 读入每一层包含的节点编号 60 61graph = new int*[N]; 62fa = new int[N]; 63for (int i = 0; i < N; i ++){ 64graph[i] = new int[N]; 65fa[i] = i;//初始化前驱节点,方便记录路径 66for (int j = 0; j < N; j ++){ 67graph[i][j] = INF; 68} 69}// 初始化输入输出 70 71for (int i = 0; i < T - 1; i ++){ 72int sz_1 = Nodes[i].size(), sz_2 = Nodes[i + 1].size(); 73for (int j = 0; j < sz_1; j ++){ 74for (int k = 0; k < sz_2; k ++){ 75scanf("%d", &graph[Nodes[i][j]][Nodes[i + 1][k]]); 76} 77} 78}// 读入每一层结点与下层节点之间的距离 79 80for (int i = 0; i < Nodes[0].size(); i ++) dp[0][Nodes[0][i]] = 0;// 初始化边界,到达出发点花费为0 81for (int i = 1; i < T; i ++){ 82int sz_1 = Nodes[i].size(), sz_2 = Nodes[i - 1].size(); 83for (int j = 0; j < sz_1; j ++){ 84int x = Nodes[i][j]; 85for (int k = 0; k < sz_2; k ++){ 86int y = Nodes[i - 1][k]; 87//dp[i][x] = min(dp[i][x], dp[i - 1][y] + graph[y][x]); 88if (dp[i][x] > dp[i - 1][y] + graph[y][x]){ 89dp[i][x] = dp[i - 1][y] + graph[y][x];// 更新dp方程 90fa[x] = y;// 记录路径 91} 92} 93} 94} 95for (int i = 0; i < Nodes[T - 1].size(); i ++){ 96printf("%d\n", dp[T - 1][Nodes[T - 1][i]]); 97int x = Nodes[T - 1][i]; 98print(x); 99printf("\n");100}// 输出路径以及结果 101}

-The End-

文案 / 贺兴(大四)

排版 / 贺兴(大四)

代码 / 贺兴(大四)

审核 / 贺兴(大四)

指导老师 / 秦时明岳

如对代码有疑问,可联系小编,可以提供有偿辅导服务。PS:部分资料来自网络。

贺兴(华中科技大学管理学院本科四年级、hexing15@gmail.com)

本文分享自微信公众号 - 数据魔术师(data-magician),作者:贺兴

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-09-15

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

免责声明:非本网注明原创的信息,皆为程序自动获取互联网,目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责;如此页面有侵犯到您的权益,请给站长发送邮件,并提供相关证明(版权证明、身份证正反面、侵权链接),站长将在收到邮件12小时内删除。

相关阅读

一周热门

查看更多