[백준] 12920번 - 평범한 배낭 2 [Java][C++]

문제 링크

---

1. 문제 풀이

최대 $M$ 만큼의 무게를 넣을 수 있는 배낭이 있고 각 물건이 여러 개 존재할 때 만족도의 최댓값을 찾는 문제다. 물건의 종류가 $N$ 이고, 각 물건의 개수가 $K$ 개인데 둘의 곱이 최대 $1,000,000$ 이고 $M$ 도 최대 $10,000$ 이어서 각 물건 하나하나마다 0／1 배낭 문제를 적용하면 시간 내에 해결할 수 없다.

해당 문제는 다중 배낭 문제 알고리즘을 적용하면 해결할 수 있는데 각 종류에 대해 이진 분할로 그룹을 나누어서 0／1 배낭 문제로 효율적으로 변형하는 것이 핵심이다.

$i$ 번째 물건의 개수가 $k_i$ 일 때, $\displaystyle \sum_{i=1}^{N} k_i$ 만큼의 물건으로 나누지 말고 $\displaystyle \sum_{i=1}^{N} \log k_i$ 만큼의 물건으로 나누어야 한다.

이진 그룹핑을 위해 비트 연산으로 $1$ 부터 $2$ 의 거듭제곱을 계속 빼주면서 그룹을 만들어줬다. 이후 나머지가 존재할 경우에 추가로 넣어줬고 이렇게 만들어진 전체 물건 그룹에 대한 0／1 배낭 문제를 적용하면 해결할 수 있다.

---

2. 코드

1. Bottom-Up 2차원 dp [Java]

import java.io.*;
import java.util.*;

public class Main {

    static class Item {
        int V;
        int C;

        public Item(int V, int C) {
            this.V = V;
            this.C = C;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        List<Item> items = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int V = Integer.parseInt(st.nextToken());
            int C = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());

            // 이진 그룹핑
            for (int bit = 1; bit <= K; bit <<= 1) {
                items.add(new Item(V * bit, C * bit));
                K -= bit;
            }

            // 나머지가 존재하면 그룹핑
            if (K != 0) {
                items.add(new Item(V * K, C * K));
            }
        }

        int[][] dp = new int[1 + items.size()][1 + M];
        for (int i = 1; i <= items.size(); i++) {
            int v = items.get(i - 1).V;
            int c = items.get(i - 1).C;

            for (int j = 1; j <= M; j++) {
                if (j < v) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j - v] + c, dp[i - 1][j]);
                }
            }
        }

        System.out.println(dp[items.size()][M]);
    }
}

2. Bottom-Up 1차원 dp [Java]

이진 그룹핑을 적용하면 0／1 배낭 문제라서 1차원 dp는 역방향 탐색으로 진행했다.

import java.io.*;
import java.util.*;

public class Main {

    static class Item {
        int V;
        int C;

        public Item(int V, int C) {
            this.V = V;
            this.C = C;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        List<Item> items = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int V = Integer.parseInt(st.nextToken());
            int C = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());

            // 이진 그룹핑
            for (int bit = 1; bit <= K; bit <<= 1) {
                items.add(new Item(V * bit, C * bit));
                K -= bit;
            }

            // 나머지가 존재하면 그룹핑
            if (K != 0) {
                items.add(new Item(V * K, C * K));
            }
        }

        int[] dp = new int[1 + M];
        for (Item item : items) {
            int v = item.V;
            int c = item.C;

            for (int j = M; j >= v; j--) {
                dp[j] = Math.max(dp[j - v] + c, dp[j]);
            }
        }

        System.out.println(dp[M]);
    }
}

3. Bottom-Up 2차원 dp [C++]

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<pair<int, int>> a;
    for (int i = 0; i < n; i++) {
        int v, c, k;
        cin >> v >> c >> k;

        // 이진 그룹핑
        for (int bit = 1; bit <= k; bit <<= 1) {
            a.emplace_back(v * bit, c * bit);
            k -= bit;
        }

        // 나머지가 존재하면 그룹핑
        if (k) {
            a.emplace_back(v * k, c * k);
        }
    }

    vector<vector<int>> dp(1 + a.size(), vector<int>(1 + m));
    for (int i = 1; i <= a.size(); i++) {
        int v = a[i - 1].first;
        int c = a[i - 1].second;

        for (int j = 1; j <= m; j++) {
            if (j < v) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = max(dp[i - 1][j - v] + c, dp[i - 1][j]);
            }
        }
    }

    cout << dp[a.size()][m];
}

4. Bottom-Up 1차원 dp [C++]

이진 그룹핑을 적용하면 0／1 배낭 문제라서 1차원 dp는 역방향 탐색으로 진행했다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<pair<int, int>> a;
    for (int i = 0; i < n; i++) {
        int v, c, k;
        cin >> v >> c >> k;

        // 이진 그룹핑
        for (int bit = 1; bit <= k; bit <<= 1) {
            a.emplace_back(v * bit, c * bit);
            k -= bit;
        }

        // 나머지가 존재하면 그룹핑
        if (k) {
            a.emplace_back(v * k, c * k);
        }
    }

    vector<int> dp(1 + m);
    for (auto p : a) {
        int v = p.first;
        int c = p.second;

        for (int j = m; j >= v; j--) {
            dp[j] = max(dp[j - v] + c, dp[j]);
        }
    }

    cout << dp[m];
}

---

3. 풀이 정보

1. Bottom-Up 2차원 dp [Java]

언어	시간	메모리	코드 길이
Java 11	204 ms	69420 KB	1668 B

2. Bottom-Up 1차원 dp [Java]

언어	시간	메모리	코드 길이
Java 11	152 ms	18120 KB	1456 B

3. Bottom-Up 2차원 dp [C++]

언어	시간	메모리	코드 길이
C++ 17	56 ms	56880 KB	969 B

4. Bottom-Up 1차원 dp [C++]

언어	시간	메모리	코드 길이
C++ 17	12 ms	2184 KB	769 B

---