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

문제 링크

---

1. 문제 풀이

최대 $K$ 만큼의 무게를 담을 수 있는 배낭에 주어진 물건들을 담을 때 물건의 가치의 합이 최대가 되게 하는 문제다. 물건의 수가 최대 $100$ 개로 각 물건을 담거나 안담는 브루트 포스로는 경우의 수가 $2^{100}$ 으로 시간 초과가 발생한다. 문제 설명부터 힌트가 있는데 각 물건을 담거나 안담는 두 가지 경우를 효율적으로 처리할 수 있는 0／1 배낭 문제 알고리즘을 적용하면 해결할 수 있다.

---

2. 코드

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

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

public class Main {
    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 K = Integer.parseInt(st.nextToken());

        int[] W = new int[1 + N];
        int[] V = new int[1 + N];
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            W[i] = Integer.parseInt(st.nextToken());
            V[i] = Integer.parseInt(st.nextToken());
        }

        int[][] dp = new int[1 + N][1 + K];
        for (int i = 1; i <= N; i++) {
            int w = W[i];
            int v = V[i];

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

        System.out.println(dp[N][K]);
    }
}

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

0／1 배낭 문제라서 1차원 dp는 역방향 탐색으로 진행했다.

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

public class Main {
    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 K = Integer.parseInt(st.nextToken());

        int[] W = new int[N];
        int[] V = new int[N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            W[i] = Integer.parseInt(st.nextToken());
            V[i] = Integer.parseInt(st.nextToken());
        }

        int[] dp = new int[1 + K];
        for (int i = 0; i < N; i++) {
            int w = W[i];
            int v = V[i];

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

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

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, k;
    cin >> n >> k;

    vector<pair<int, int>> a(n);
    for (auto& p : a) cin >> p.first >> p.second;

    vector<vector<int>> dp(1 + n, vector<int>(1 + k));
    for (int i = 1; i <= n; i++) {
        int w = a[i - 1].first;
        int v = a[i - 1].second;

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

    cout << dp[n][k];
}

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, k;
    cin >> n >> k;

    vector<pair<int, int>> a(n);
    for (auto& p : a) cin >> p.first >> p.second;

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

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

    cout << dp[k];
}

---

3. 풀이 정보

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

언어	시간	메모리	코드 길이
Java 11	172 ms	53836 KB	1093 B

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

언어	시간	메모리	코드 길이
Java 11	128 ms	14600 KB	933 B

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

언어	시간	메모리	코드 길이
C++ 17	36 ms	42004 KB	639 B

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

언어	시간	메모리	코드 길이
C++ 17	8 ms	2412 KB	460 B

---