Subset sum problem (With quantity limitations)
(Mylib/Typical/subset_sum_limited.cpp)

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

Operations

• subset_sum_limited(N, K, a[N], m[N])
  • Time complexity $O(NK)$

Requirements

Notes

Problems

• AOJ 2955 Two Colors Sort

References

• 蟻本第2版 P62~63

Verified with

• test/aoj/2370/main.test.cpp
• test/aoj/2955/main.test.cpp

Code

#pragma once
#include <cassert>
#include <vector>

namespace haar_lib {
  auto subset_sum_limited(int N, int K, const std::vector<int> &a, const std::vector<int> &m) {
    assert((int) a.size() == N and (int) m.size() == N);
    std::vector<int> dp(K + 1, -1);

    dp[0] = 0;
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j <= K; ++j) {
        if (dp[j] >= 0) {
          dp[j] = m[i];
        } else if (j < a[i] or dp[j - a[i]] <= 0) {
          dp[j] = -1;
        } else {
          dp[j] = dp[j - a[i]] - 1;
        }
      }
    }

    for (int i = 0; i <= K; ++i) dp[i] = dp[i] >= 0;

    return dp;
  }
}  // namespace haar_lib

#line 2 "Mylib/Typical/subset_sum_limited.cpp"
#include <cassert>
#include <vector>

namespace haar_lib {
  auto subset_sum_limited(int N, int K, const std::vector<int> &a, const std::vector<int> &m) {
    assert((int) a.size() == N and (int) m.size() == N);
    std::vector<int> dp(K + 1, -1);

    dp[0] = 0;
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j <= K; ++j) {
        if (dp[j] >= 0) {
          dp[j] = m[i];
        } else if (j < a[i] or dp[j - a[i]] <= 0) {
          dp[j] = -1;
        } else {
          dp[j] = dp[j - a[i]] - 1;
        }
      }
    }

    for (int i = 0; i <= K; ++i) dp[i] = dp[i] >= 0;

    return dp;
  }
}  // namespace haar_lib

Back to top page