Skip to content

Instantly share code, notes, and snippets.

@yanjinbin
Created July 9, 2020 15:36
Show Gist options
  • Save yanjinbin/6ffffe11d0d33ed6af89c322b5a118f9 to your computer and use it in GitHub Desktop.
Save yanjinbin/6ffffe11d0d33ed6af89c322b5a118f9 to your computer and use it in GitHub Desktop.
#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限制下 剩余价值,
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;
}
// index 表示索引,time 表示剩余实践。
void dfs(int index, int time, int v) {
ans = max(ans, v);
if (index > m) return;// 可行性剪枝
if (f(index, time) + v > ans) // 不取,最优性剪枝 解释意味着我不取得情况下,后续能取最大价值能不能大于目前最大得价值
dfs(index + 1, time, v);
if (node[index].time <= time) // 可行性剪枝
dfs(index + 1, time - node[index].time, v + node[index].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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment