Knapsack problem (With quantity limitations)
(Mylib/Typical/knapsack_limited.cpp)

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Link: View error logs on GitHub Actions

Operations

• knapsack_limited(int N, Weight cap, Weight w[N], Value v[N], int m[N])
  • 個数制限ナップサック問題を解く。
  • Time complexity $O(N cap \log \max m)$

Requirements

Notes

Problems

• AOJ DPL_1_G Knapsack Problem with Limitations

References

Verified with

• test/aoj/DPL_1_G/main.test.cpp

Code

#pragma once
#include <algorithm>
#include <vector>

namespace haar_lib {
  template <typename Weight, typename Value>
  Value knapsack_limited(int N, Weight cap, const std::vector<Weight> &w, const std::vector<Value> &v, const std::vector<int> &m) {
    std::vector<Value> dp(cap + 1);

    for (int i = 0; i < N; ++i) {
      for (int64_t a = 1, x = m[i], k; k = std::min(x, a), x > 0; x -= k, a *= 2) {
        for (int j = cap; j >= 0; --j) {
          if (j - k * w[i] >= 0) {
            dp[j] = std::max(dp[j], dp[j - k * w[i]] + (Weight) k * v[i]);
          }
        }
      }
    }

    return dp[cap];
  }
}  // namespace haar_lib

#line 2 "Mylib/Typical/knapsack_limited.cpp"
#include <algorithm>
#include <vector>

namespace haar_lib {
  template <typename Weight, typename Value>
  Value knapsack_limited(int N, Weight cap, const std::vector<Weight> &w, const std::vector<Value> &v, const std::vector<int> &m) {
    std::vector<Value> dp(cap + 1);

    for (int i = 0; i < N; ++i) {
      for (int64_t a = 1, x = m[i], k; k = std::min(x, a), x > 0; x -= k, a *= 2) {
        for (int j = cap; j >= 0; --j) {
          if (j - k * w[i] >= 0) {
            dp[j] = std::max(dp[j], dp[j - k * w[i]] + (Weight) k * v[i]);
          }
        }
      }
    }

    return dp[cap];
  }
}  // namespace haar_lib

Back to top page