knapsack

knapsack.cc

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <functional>
#include <algorithm>
#include <numeric>

using namespace std;

#define all(c) c.begin(),c.end()

struct knapsack {
  int W;
  struct item { 
    int v, w; 
  };
  vector<item> items;
  void add_item(int v, int w) {
    items.push_back({v, w});
  }
  int lv;
  int solve_rec(size_t k, int v, int w) {
    if (w + items[k].w > W) return solve_rec(k+1, v, w);
    int cv = v, cw = w;
    for (size_t i = k; i < items.size(); ++i) {
      if (cw + items[i].w <= W) {
        cw += items[i].w;
        cv += items[i].v;
      }
    }
    if (lv < cv) lv = cv;
    double fv = v, fw = w;
    for (size_t i = k; i < items.size(); ++i) {
      if (fw + items[i].w <= W) {
        fw += items[i].w;
        fv += items[i].v;
      } else {
        fv += items[i].v * (W - fw) / items[i].w;
        break;
      }
    }
    //fprintf(stderr, "  lower=%d, curr(%d/%d)=%d, upper=%f\n", lv, v, k, items.size(), fv);
    if (fv - lv < 1 || fv < lv) return lv;
    solve_rec(k+1, v+items[k].v, w+items[k].w);
    return solve_rec(k+1, v, w);
  }
  int solve() {
    sort(all(items), [](const item &a, const item &b) { 
      return a.v * b.w > a.w * b.v;
    });
    lv = 0;
    return solve_rec(0, 0, 0);
  };
};

int main() {
  int T; 
  scanf("%d", &T);
  for (size_t t = 0; t < T; ++t) {
    if (t > 0) printf("\n");
    int W, n;
    scanf("%d %d", &W, &n);
    vector<int> v(n), w(n);
    for (int i = 0; i < n; ++i) 
      scanf("%d %d", &w[i], &v[i]);

    knapsack solver;
    solver.W = W;
    for (int i = 0; i < n; ++i)
      solver.add_item(v[i], w[i]);
    printf("%d", solver.solve());
  }
}