Heuristic Search

Problem statement: There are $N$ types of items and a knapsack with capacity $W$. Each item has two attributes, weight $w_i$ and value $v_i$. Select some items (each item can be selected only once) to put into the knapsack, so that the total value of the items in the knapsack is maximized while their total weight does not exceed the capacity of the knapsack.

We write an evaluation function $f$ that can prune all invalid $0$ branches (that is, prune a large number of useless branches where an item is not selected).

The execution process of the evaluation function $f$ is as follows:

When taking an item, check whether the specified capacity is exceeded (feasibility pruning); when not taking an item, check whether the total value of the remaining herbs plus the current value is greater than the best solution found so far (optimality pruning).

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

struct Node {
  int a, b;  // a represents time, b represents value
  double f;
} node[N];

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

int f(int t, int v) {  // calculate the maximum value of the remaining items at the current time
  int 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 (int)(tot + v * node[t + i].f);
  return tot;
}

void work(int t, int p, int v) {
  ans = max(ans, v);
  if (t > n) return;                         // boundary condition: there are only n types of items
  if (f(t, p) + v > ans) work(t + 1, p, v);  // optimality pruning
  if (node[t].a <= p) work(t + 1, p - node[t].a, v + node[t].b);  // feasibility pruning
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  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 is the value-to-weight ratio
  }
  sort(node + 1, node + n + 1);  // sort by value-to-weight ratio
  work(1, m, 0);
  cout << ans << '\n';
  return 0;
}