当前位置:   article > 正文

动态规划思想的实际应用_动态规划算法可以解决那些生活中的问题

动态规划算法可以解决那些生活中的问题

改编自

改编自洛谷题库 P1048采药 https://www.luogu.com.cn/problem/P1048

问题描述

小猪是一名天赋异禀的运动员,从小被父母送进体校进行双人运动培训(例如羽毛球、乒乓球等),小猪在漫长的9年训练过程中逐渐丧失了对双人运动的乐趣。
渐渐地,小猪发现自己喜欢的其实是多人运动(例如篮球、足球、王者荣耀等)。但由于害怕教练的责罚,小猪只能偷偷在凌晨的短暂时间内,安排自己的多人运动。
而且由于教练行踪不定,每晚能进行多人运动的时间都是不确定的。小猪进行不同的多人运动可以获得不同的快乐点,例如打篮球、足球、王者荣耀,甚至不同段位的多人运动都会产生不同的快乐点h,并且不同的运动所需要的时间t也不同。
现在小猪一个晚上有多种可选择的多人运动,聪明的你能帮助小猪在晚上有限的时间点内,完成最佳时间管理吗?

在这里插入图片描述

时间管理是一门学问

目标

在有限的时间T内,给定N个多人运动,每个多人运动有以下特点:
在这里插入图片描述
在T时间内安排合理的运动,使得小猪能获得总和最多的快乐点

输入在这里插入图片描述

输出

一个整数H,表示小猪可以获得的快乐最大值

例子

输入

240 5
20 399
221 4500
220 4120
45 5
300 558

240 5(小猪有5个可选择多人运动)
20 390 (王者青铜局,20分钟结束战斗,获得快乐399)
221 4500(打篮球,虽然要221分钟,但是可以获得4500快乐)
220 4120(打母猪焊接,虽然要220分钟,但是可以获得4120快乐)
45 5(打王者荣耀荣耀局,时间长,因为被吊打所以没有什么快乐)
300 558 (崩300分钟的迪,快乐558)

标准答案 4510

分析问题和找到解法

分析

首先 时间是有限的,所以显然我们只能在诸多可能的运动中选择 如果小猪很贪心,直接进行快乐点最多的运动,那么小猪有没有可能直接获得最多的快乐呢?

答案是有可能的,但是不能代表全部的情况。 例如上面的例子,显然直接去打篮球是最多快乐的,但是实际上这个决策只能带来4500的快乐,而比不上打一局青铜王者和母猪焊接一起的4510点快乐来的多,因为浪费了19分钟无法安排任何活动。

那么
如果我们采取价值/时间来决策呢,我们会发现还是打篮球最划算,因为打篮球的价值/时间比是最多的,**然而我们无法达到最多的4510点快乐**。

为什么呢?

我们对问题进行分析,我们最终的状态是什么?
最终的状态:
时间已经达到开始所给的T分钟
那么为什么效率最高的解法——价值/时间最高的方法不是最好的呢?
因为比如上面的例子,有时间被浪费了

那怎么办?

我们需要换个角度来思考了
最终的这个状态是怎么来的?
很显然,最后的240分钟是一分钟一分钟地从0分钟来的,
正如伟大的哲学家所说,劳力士和电子手表,时间是一样转的
不论采取那种组合时间的方式,时间一定会流向终点
比如上述例子,达到最终时间的前一步,一定是做完某一个运动之前的时间,或者一分钟前(无法做运动)在这里插入图片描述

如图,可见要达到最终状态,上一个状态可以是前一分钟(这样什么运动都做不了)
也可以从19分钟开始做(这样可以穿插安排一个打篮球或者母猪焊接)
也可以从18分钟开始做(还是可以穿插一个打篮球或者母猪焊接)
也可以从4分钟开始做(可以打篮球或者母猪焊接)
也可以从20分钟开始做(可以是母猪焊接)
因为已经是最后一步了,所以我们无脑选择这一步最优化的策略,也就是原有的快乐值+现在的快乐值之后总和最多

那么说了这么说,能保证这种做法达到的快乐值最多吗

能!!!

因为,如果我们能保证前一步的所有决策都是最优化的决策(也就是前一步的每一分钟都是最优化的决策),那么我们可以确信,我们现在的决策就是最优的

换句话说,确保过去是最优解,当前是最优解,那么就能确保未来是最优解。
但是现在的过去相当于过去的现在,所以过去要保证过去的过去是最优化的,过去的过去要保证过去的过去的过去要是最优化的。
禁止套娃 层层套娃,直到不能再套——回到了原点(在本题中就是回到了时间为0的位置)

时间为0,快乐值为0,这一状态有着绝对正确的性质
在这里插入图片描述

在这里插入图片描述

动态规划

核心就是 我是谁,我从哪里来,我到哪里去,把大问题无限分割
只要保证每一个小问题绝对正确,那么大问题绝对正确
在这里插入图片描述
小学课文《走一步,再走一步》深刻挖掘了这种思想

状态转移方程

在这里插入图片描述

这样做可能遇到的问题?

这样子可能会遇到重复的问题,也就是说,一个“很好的”运动可能会被用多次

做一点小改进吧

因为如果决策中的运动一样,那么进行这些运动的顺序其实是没有关系的,所以我们可以利用这个特性,把最终的状态定义为
当了解到第N个运动的时候,最佳的决策
也就是说,我们从第一个可能的运动开始遍历,第1个第2个、一直到第N个运动,保证了解到第K个可能的运动的时候我们的决策始终是最佳的

那么我们的状态转移方程就是

在这里插入图片描述

我们来结合具体例子看一看 首先小猪来了解王者青铜局
由于当前时间充裕,所以此时dp[1][20]之后的比如 dp[1][21] dp[1][22] dp[1][23] 一直到 dp[1][240] 都是20
我们取dp[1][240]出来,解释为此时最佳决策
然后我们再来看下一个运动打篮球
也可以从20分钟开始做(可以是母猪焊接)

**我们来对比一下

max(dp[1][221] (399), dp[1][19]+va[2] (0+4500))
  • 1

显然dp[2][221]应该被更新为后者**

也就是说,对于小猪看到打篮球这个第二个运动的时候,小猪发现,原来比起打王者荣耀,还是打篮球更赚喔(小猪是不会考虑以后的,他只考虑当下)

所以当小猪看到可以打母猪焊接的时候,小猪发现

比起dp[2][240],更加应该被更新为 dp[2][20](已经打了王者)+vi[3](母猪焊接)
  • 1

之后采取任何决策都不会比这个决策更好了

在这里插入图片描述

C++代码实现

#include<bits/stdc++.h>
#define ios std::ios::sync_with_stdio(false)
using namespace std;
int va[105];//用来存储运动相应的价值
int ti[105];//用来存存储运动相应的时间
int dp[1050][1050];//用来存储进行到第t1时间时,前一状态的t2时间最大价值
signed main()
{
	ios;
	int T, N;
	cin >> T >> N;//输入时间t和可选择的项目n
	for (int i = 1; i <= N; i++)
	{
		cin >> ti[i] >> va[i];
	}
	for (int k = 1; k <= N; k++)
	{
		for (int t = 0; t <= T; t++)
		{
			dp[k][t] = dp[k - 1][t];//先假设上一个决策即使到了现在还是对的
			if (t - ti[k] >= 0)
				dp[k][t] = max(dp[k][t], dp[k - 1][t - ti[k]] + va[k]);//如果加上现在决策更好那就换
		}
	}
	
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= T; j++)
		{
			cout << dp[i][j] << " ";
		}
		cout << endl;
	}
	cout << dp[N][T] << endl;
	return 0;
}
  • 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

我是冷萃泡泡茶,下期再会

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/770377
推荐阅读
相关标签
  

闽ICP备14008679号