题解 | #Beautiful Land#

这题是经典的启发式搜索，我们首先要将每棵树按单位价值降序排序。然后，dfs每棵树是否选取，通过计算在当前空间下剩余物品的可能的最大价值来进行剪枝，该最大价值不能使答案更大，就不进行跳过这颗树的dfs。

#include <iostream>
using namespace std;
constexpr int N = 105;
typedef long long ll;
ll n, m, ans;

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

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

ll f(ll t, ll v) {  // 计算在当前空间下，剩余物品的最大价值
  ll tot = 0;
  for (int i = 1; t + i <= n; i++)
    if (v >= node[t + i].a) {
      v -= node[t + i].a;
      tot += node[t + i].b;
    } else
      return (ll)(tot + v * node[t + i].f);
  return tot;
}

void work(ll t, ll p, ll v) {
  ans = max(ans, v);
  if (t > n) return;                         // 边界条件：只有n种物品
  if (f(t, p) + v > ans) work(t + 1, p, v);  // 最优性剪枝
  if (node[t].a <= p) work(t + 1, p - node[t].a, v + node[t].b);  // 可行性剪枝
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int t;
  cin >> t;
  while (t--)
  {
    ans = 0;
    cin >> n >> m;
    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 + n + 1);  // 根据性价比排序
    work(1, m, 0);
    cout << ans << '\n';
  }
  return 0;
}