bitset unbounded knapsack

$n$개의 수 $x_1, x_2, ..., x_n$ 중 일부의 합이 $k$가 될 수 있는지 판별하는 0/1 knapsack 문제를 bitset으로 최적화하는 방법은 잘 알려져 있습니다.

bool knapsack(const vector<int> &v, int n, int k) {
    vector<bool> dp(k + 1);
    dp[0] = 1;
    for (auto e : v) {
        for (int i = k; i >= e; i--) if (dp[i - e]) dp[i] = true;
    }
    return dp[k];
}

// bitset으로 최적화
bool knapsack(const vector<int> &v, int n, int k) {
    bitset<MAX_K> dp;
    dp[0] = 1;
    for (auto e : v) dp |= dp << e;
    return dp[k];
}

 

이제 각각의 $x_i$들을 무제한으로 사용할 수 있는 unbounded knapsack을 풀어봅시다. 먼저 naive 코드입니다.

bool knapsack(const vector<int> &v, int n, int k) {
    vector<bool> dp(k + 1);
    dp[0] = 1;
    for (auto e : v) {
        for (int i = e; i <= k; i++) if (dp[i - e]) dp[i] = true;
    }
    return dp[k];
}

 

단순히 for문을 bitset으로 바꾸려하면 쉽지 않고, 아이디어가 하나 필요합니다.

unbounded knapsack은 binary split을 통해 0/1 knapsack으로 변환할 수 있다는 점입니다.
$x_i$를 무제한으로 사용할 수 있다는 것은 $x_i$를 $1, 2, 4, 8, ...$개씩 묶어 별개의 물건으로 취급하는 것과 같습니다. 즉, $x_i \times 2^j \le k$인 모든 j에 대해 $x_i \times 2^j$의 무게를 가진 물건들을 최대 한 번씩 사용하는 0/1 Knapsack으로 생각할 수 있습니다.

bool knapsack(const vector<int> &v, int n, int k) {
    bitset<MAX_K> dp;
    dp[0] = 1;
    for (auto e : v) {
        for (; e <= k; e <<= 1) dp |= dp << e;
    }
}

 

for (; e <= k; e <<= 1)의 반복횟수는 $\left( 1 + \left\lfloor \log ( \dfrac{k}{e} ) \right\rfloor \right)$번이고, k가 int범위이므로(애초에 long long범위라면 knapsack으로 안되기 때문에) 최대 30번 정도 반복됩니다. 하지만 bitset을 사용함으로써 naive에 비해 얻는 시간적 이득이 64배이므로 결과적으로는 이득입니다.

 

 

아래는 unbounded knapsack을 사용할 수 있는 문제입니다.

https://www.acmicpc.net/problem/22101