启发式搜索

启发式搜索

[NOIP2005 普及组] 采药

题目描述

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

如果你是辰辰，你能完成这个任务吗？

输入格式

第一行有 个整数 （）和 （），用一个空格隔开， 代表总共能够用来采药的时间， 代表山洞里的草药的数目。

接下来的 行每行包括两个在 到 之间（包括 和 ）的整数，分别表示采摘某株草药的时间和这株草药的价值。

输出格式

输出在规定的时间内可以采到的草药的最大总价值。

样例 #1

样例输入 #1

1
2
3
4
70 3
71 100
69 1
1 2

样例输出 #1

1
3

提示

【数据范围】

  • 对于 的数据，；
  • 对于全部的数据，。

【题目来源】

NOIP 2005 普及组第三题

题解

  • 启发式函数的作用是基于已有的信息,对搜索的每一个分支选择都做估价，进而选择分支。简单来说，启发式搜索就是对取和不取都做分析，从中选取更优解或删去无效解。
  • 贪心选择物品：从第 个物品开始依次选择物品。对于每个物品 ，如果其所需的时间 小于或等于当前剩余时间 ，则选择该物品并扣除相应的时间 ，并将该物品的价值加到总价值 中，即 。
  • 部分选择物品：如果某个物品的时间需求 大于剩余时间 ，则不能完整选择该物品。但是我们可以选择一部分时间来获取部分价值。这个部分价值根据该物品的性价比 来计算，即 。
  • 完全选择物品的情况：如果循环结束且剩余时间足够支撑完整的物品选择，则返回累计的总价值 。
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <algorithm>

using namespace std;
const int N = 105; 
int n, m, ans;

struct Node {
	int a, b; // a 代表时间，b 代表价值
	double f;
} node[N];

bool operator<(Node p, Node q) { return p.f > q.f; }

// 估价函数 f，可以剪掉所有无效的枝条
// thinkn: 当前已经考虑过的物品数量。也就是说，node[1] 到 node[t] 已经被考虑过了。
// times: 剩余可用的时间。即在处理了前 t 个物品后，还剩下多少时间可以分配给后续物品。
int f(int thinkn, int times) {  // 计算在当前时间下，剩余物品的最大价值
  int tot = 0;
  for (int i = 1; thinkn + i <= n; i++)
    if (times >= node[thinkn + i].a) {
      times -= node[thinkn + i].a;
      tot += node[thinkn + i].b;
    } else
      return (int)(tot + times * node[thinkn + i].f);
  return tot;
}

// value 当前拿到的价值 
// 可行性剪枝：如果当前物品的时间消耗 node[t].a 不超过当前剩下时间，则尝试选择该物品。
// 最优性剪枝：如果估算未来价值加上当前价值，超过当前已知的最大值 ans 就不选当前的继续搜索。
void work(int thinkn, int times, int value) {
	ans = max(ans, value);
	if (thinkn > n) return;                         // 边界条件：只有n种物品
	if (f(thinkn, times) + value > ans) work(thinkn + 1, times, value);  // 最优性剪枝
	if (node[thinkn].a <= times) work(thinkn + 1, times - node[thinkn].a, value + node[thinkn].b);  // 可行性剪枝
}

int main() {
	
	cin >> m >> n;
	
	for(int i = 1; i <= n ; i ++ ) {
		cin >> node[i].a >> node[i].b;
		node[i].f = 1.0 * node[i].b / node[i].a;  // f为性价比
	}
	
	sort(node + 1, node + 1 + n);
	work(1, m, 0);
	
	cout << ans;
	
	return 0;
}