0-1 ナップサック問題 (半分全列挙) (src/Optimization/Knapsack.hpp)

View this file on GitHub
View document part on GitHub
Last update: 2023-04-02 00:58:03+09:00
Include: #include "src/Optimization/Knapsack.hpp"

計算量が n 倍改善されてるやつ
空間計算量的にも n は 50 ぐらいが限界か

メンバ関数

名前	概要	計算量
`add(v,w)`	価値 v, 重さ w のアイテムを追加
`build()`	下準備 (半分に分けて全列挙する)	$O(2^{\frac{n}{2}})$
`solve(cap)`	容量が cap 以下になるような価値の最大値を返す (尺取)	$O(2^{\frac{n}{2}})$

参考

https://twitter.com/noshi91/status/1271857111903825920

Verify

東京海上日動プログラミングコンテスト2020 D - Knapsack Queries on a tree

Verified with

test/aoj/DPL_1_H.test.cpp

Code

#pragma once
#include <vector>
#include <algorithm>
template <class value_t, class weight_t> class Knapsack {
 std::vector<std::pair<weight_t, value_t>> I, L, R, tmp;
public:
 Knapsack() {}
 void add(value_t v, weight_t w) { I.emplace_back(w, v); }
 void build() {
  const int n= I.size(), l= n / 2, r= n - l;
  int i= 0, u, s;
  for (s= u= 1, L.resize(1 << l), tmp.resize(1 << l); i < l; std::merge(L.begin(), L.begin() + u, L.begin() + u, L.begin() + u + u, tmp.begin()), ++i, s= u<<= 1, L.swap(tmp))
   for (auto [w, v]= I[i]; s--;) L[u | s]= {L[s].first + w, L[s].second + v};
  for (s= u= 1, R.resize(1 << r), tmp.resize(1 << r); i < n; std::merge(R.begin(), R.begin() + u, R.begin() + u, R.begin() + u + u, tmp.begin()), ++i, s= u<<= 1, R.swap(tmp))
   for (auto [w, v]= I[i]; s--;) R[u | s]= {R[s].first + w, R[s].second + v};
  for (i= 1; i < u; ++i) R[i].second= std::max(R[i].second, R[i - 1].second);
 }
 value_t solve(weight_t cap) const {
  value_t ret= 0;
  int j= R.size() - 1;
  for (auto [w, v]: L) {
   if (cap < w) break;
   for (auto c= cap - w; R[j].first > c;) --j;
   ret= std::max(ret, v + R[j].second);
  }
  return ret;
 }
};

#line 2 "src/Optimization/Knapsack.hpp"
#include <vector>
#include <algorithm>
template <class value_t, class weight_t> class Knapsack {
 std::vector<std::pair<weight_t, value_t>> I, L, R, tmp;
public:
 Knapsack() {}
 void add(value_t v, weight_t w) { I.emplace_back(w, v); }
 void build() {
  const int n= I.size(), l= n / 2, r= n - l;
  int i= 0, u, s;
  for (s= u= 1, L.resize(1 << l), tmp.resize(1 << l); i < l; std::merge(L.begin(), L.begin() + u, L.begin() + u, L.begin() + u + u, tmp.begin()), ++i, s= u<<= 1, L.swap(tmp))
   for (auto [w, v]= I[i]; s--;) L[u | s]= {L[s].first + w, L[s].second + v};
  for (s= u= 1, R.resize(1 << r), tmp.resize(1 << r); i < n; std::merge(R.begin(), R.begin() + u, R.begin() + u, R.begin() + u + u, tmp.begin()), ++i, s= u<<= 1, R.swap(tmp))
   for (auto [w, v]= I[i]; s--;) R[u | s]= {R[s].first + w, R[s].second + v};
  for (i= 1; i < u; ++i) R[i].second= std::max(R[i].second, R[i - 1].second);
 }
 value_t solve(weight_t cap) const {
  value_t ret= 0;
  int j= R.size() - 1;
  for (auto [w, v]: L) {
   if (cap < w) break;
   for (auto c= cap - w; R[j].first > c;) --j;
   ret= std::max(ret, v + R[j].second);
  }
  return ret;
 }
};