[数据结构与算法][动态规划]2005年分区联赛普级组之三 采药

题目描述

辰辰是个很有潜能、天资聪颖的孩子，他的梦想是称为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是辰辰，你能完成这个任务吗？
点击前往该题

输入

输入的第一行有两个整数T（1<=T<=1000）和M（1<=M<=100），T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的的整数，分别表示采摘某株草药的时间和这株草药的价值。
（对于30%的数据，M <= 10；对于全部的数据，M <= 100。）

输出

输出只包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。

输入样例

70 3
71 100
69 1
1 2

输出样例

3

分析

很明显这是一道动态规划or深度优化搜索的题，进一步分析就会发现这其实是一道动态规划的背包问题，因为它符合了动态规划的条件：
1.状态必须满足最优化原理；即无论过去的状态和决策如何，对前面的决策所形成的当前状态而言，余下的诸决策必须构成最优策略，可以通俗地理解为子问题的局部最优将导致整个问题的全局最优。

2.状态必须满足无后效性；即某阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响。也就是说，“未来与过去无关”，当前的状态是此前历史的一个完整总结，此前的历史只能通过当前的状态去影响过程未来的演变。具体地说，如果一个问题被划分各个阶段之后，阶段 I 中的状态只能由阶段 I+1 中的状态通过状态转移方程得来，与其他状态没有关系，特别是与未发生的状态没有关系，这就是无后效性。
因此，方向已经明确，那还在等什么？开干！

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;//一维数组的做法
int t,m;
int w[10000],c[10000];//用于分别存储每种草药的收集时间与草药的价值
int f[10000];//用于存储每次行动的已收集的草药的价值
int main()
{
	cin>>t>>m;//输入时间和种类
	for(int i=1;i<=m;i++)
		cin>>w[i]>>c[i];//循环输入每种草药的搜集时间与草药的价值
	for(int i=1;i<=m;i++)//检索每种草药
		for(int j=t;j>=w[i];j--)//剩余时间是否够收集该草药,否则结束 
			f[j]=max(f[j],f[j-w[i]]+c[i]);//选择收集则剩余时间减少,价值增加,不选则不变 
	cout<<f[t];//输出最后的时间获得的价值 
	return 0;
	//三连三连三连我要三连
}

还有一种方法，但是相比第一个它更容易错误，空间复杂度也更大，就不详细讲解了。（基本算法一样）

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;//二维数组的做法
int t,m;
int w[10000],c[1000],f[10000][10000];
int main(){
	cin>>t>>m;
	for (int i=1;i<=m;i++)
		cin>>w[i]>>c[i];
	for (int i=1;i<=m;i++)
		for (int j=1;j<=t;j++)
		if (j>=w[i])
			f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+c[i]); 	
		else
			f[i][j]=f[i-1][j];//若不满足,保证结果不为0不影响后面计算 
	cout<<f[m][t];
	return 0;
	//三连三连三连我要三连
}

emmmm，水的 差不多了，就酱吧QwQ
给个三连嘛geigei