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

改编自

问题描述

目标

在有限的时间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分钟来的，
正如伟大的哲学家所说，劳力士和电子手表，时间是一样转的
不论采取那种组合时间的方式，时间一定会流向终点
比如上述例子，达到最终时间的前一步，一定是做完某一个运动之前的时间，或者一分钟前（无法做运动）

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

能！！！

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

换句话说，确保过去是最优解，当前是最优解，那么就能确保未来是最优解。

但是现在的过去相当于过去的现在，所以过去要保证过去的过去是最优化的，过去的过去要保证过去的过去的过去要是最优化的。

禁止套娃 层层套娃，直到不能再套——回到了原点（在本题中就是回到了时间为0的位置）

时间为0，快乐值为0，这一状态有着绝对正确的性质

动态规划

核心就是 我是谁，我从哪里来，我到哪里去，把大问题无限分割
只要保证每一个小问题绝对正确，那么大问题绝对正确

小学课文《走一步，再走一步》深刻挖掘了这种思想

状态转移方程

这样做可能遇到的问题？

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

做一点小改进吧

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

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

**我们来对比一下

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

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