01 背包的二进制优化

也是在刷题的时候发现的,比如 hiho week 195。一眼看过去就是一个 0-1 背包问题,然后直接 DP 上了,当时觉得应该问题不大,结果最后只有 50%,一看数据,100% 的数据为 1E5 量,简单的 DP 的话复杂度为 O(MN),这样复杂度估计是 1E10,这样肯定会 TLE。

然后一看,他的单个商品的全权值很低,都在 [1, 10] 之间,这样的话,最多有 100 种组合,所以极端情况下,每个商品都会有 1000 个同类。这样就有了二进制优化的余地。简单的说就是,将多个重复的商品进行优化。比如 p(w, v) 的商品有 10 个,那么,我们可以将其简化为,一个 p(1w, 1v),一个 p(2w, 2v),一个 p(4w, 4v),最后剩下一个 p(3w, 3v)。

这样的话,就将数据量从 10 简化到了 4。于是乎,就可以将数据量减少一个数量级。所以,最后这题的代码:

using namespace std;

typedef pair<uint64_t, uint64_t> pii;
typedef pair<pii, uint64_t> ppiii;
typedef pair<pii, pii> ppiipii;

int main() {
  ios::sync_with_stdio(false);
  uint64_t n, m;
  cin >> n >> m;

  map<pii, uint64_t> _ticks;
  for (uint64_t i = 0; i < n; i++) {
    uint64_t w, p;
    cin >> w >> p;
    _ticks[pii(w, p)]++;
  }

  vector<pii> ticks;
  for (auto tick : _ticks) {
    uint64_t idx    = 0;
    uint64_t remain = tick.second;

    while (remain > 0) {
      uint64_t cur = pow(2, idx);
      idx++;
      if (remain >= cur) {
        ticks.push_back(pii(cur * tick.first.first, cur * tick.first.second));
      } else {
        ticks.push_back(
            pii(remain * tick.first.first, remain * tick.first.second));
        cur = remain;
      }
      remain = remain - cur;
    }
  }

  vector<vector<uint64_t>> DP(2, vector<uint64_t>(m + 1, 0));
  for (uint64_t i = ticks[0].first; i <= m; i++) {
    DP[0][i] = ticks[0].second;
  }

  for (uint64_t i = 1; i < (uint64_t)ticks.size(); i++) {
    uint64_t cur = i % 2;
    uint64_t pre = (i - 1) % 2;

    for (uint64_t j = 0; j < ticks[i].first; j++) {
      DP[cur][j] = DP[pre][j];
    }

    for (uint64_t j = ticks[i].first; j <= m; j++) {
      DP[cur][j] =
          max(DP[pre][j - ticks[i].first] + ticks[i].second, DP[pre][j]);
    }
  }

  cout << DP[(ticks.size() - 1) % 2][m] << endl;

  return 0;
}

最后这题 AC。

Leave a Reply

Your email address will not be published. Required fields are marked *