heuristic_search.cpp

#include <algorithm>
#include <iostream>
// https://oi-wiki.org/search/heuristic/
// heuristic-search 启发式搜索
using namespace std;
const int N = 105;
int m, t, ans;
struct Node {
	int time, value;
	double f;
} node[N];

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

// f 估价函数 time限制下，不取idx,去i[dx+1,m]的剩余总价值，
int f(int idx, int time) {
	int tot = 0;
	for (int i = 1; idx + i <= m; i++)
		if (time >= node[idx + i].time) {
			time -= node[idx + i].time;
			tot += node[idx + i].value;
		} else
			return (int) (tot + time * node[idx + i].f);
	return tot;
}

void dfs(int idx, int time, int v) {
	ans = max(ans, v);
	if (idx > m) return;// 可行性剪枝
	if (f(idx, time) + v > ans) // 不取，最优性剪枝. 解释: 意味着我不取得情况下，后续能取最大价值能不能大于目前最大得价值!
		dfs(idx + 1, time, v);
	if (node[idx].time <= time) // 可行性剪枝
		dfs(idx + 1, time - node[idx].time, v + node[idx].value);
}

int main() {
	cin >> t >> m;
	for (int i = 1; i <= m; i++) {
		cin >> node[i].time >> node[i].value;
		node[i].f = 1.0 * node[i].value / node[i].time;
	}
	sort(node + 1, node + m + 1);
	dfs(1, t, 0);
	cout << ans << endl;
	return 0;
}