[BOJ][C++] 백준 12865번: 평범한 배낭

문제

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

 

문제 이해

• 최대 무게(K)가 정해진 배낭에 물건을 넣는다.
• N개의 물건에는 각각 무게(W)와 가치(V)가 있다.
• 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 구한다.

 

문제 풀이

❔ 브루트포스

• 물건의 가능한 모든 조합을 구한다.
• N개의 물건에 대해 넣을지 말지를 모두 시도한다.
• O(2^N)이고, N ≤ 100이므로 제한시간 초과

 

❔ 백트래킹

• 물건의 가능한 모든 조합을 구하면서 최대 무게를 넘어가는 경우를 가지치기로 줄인다.
• 최악의 경우로, 모든 조합이 최대 무게를 넘어가지 않으면, 브루트포스와 같아진다.

 

💡 Dynamic Programming

DP를 통해 이전 결과를 저장해서 중복 계산을 피한다.

• '배낭의 최대 무게'를 인덱스로, 가치합의 최댓값을 저장한다.
• N개의 물건을 탐색하면서, 현재 물품을 배낭에 넣는 경우, 넣지 않는 경우 중에 최댓값을 저장한다.
• 배낭에 넣는 경우: 현재 물품의 무게를 뺐을 때 가치합의 최댓값 + 현재 물품의 가치
  배낭에 넣지 않는 경우: 기존에 저장되어 있는 값

 

💡 DP 점화식

각 i번째 물건에 대해, 무게 j에서 최대 가치를 갱신한다. (물건 범위: 0 ~ N / 무게 범위: 0 ~ K)

// j >= item[i].w
dp[i][j] = max(dp[i - 1][j - item[i].w] + item[i].v, dp[i - 1][j])

 

 

해당 물품을 여러 번 사용하는 것을 방지하기 위해, 각 물품을 행으로 구분해서 2차원 배열을 사용했다.

그런데 역순으로 저장하면 1차원 배열로 구현할 수 있다.

dp[j] = max(dp[j - item[i].w] + item[i].v, dp[j])

 

 

🎒 냅색 문제(Knapsack Problem)

1. 0-1 Knapsack
   • 각 물건은 한 번만 선택 가능
   • "넣거나 말거나" → 선택지는 0 또는 1
2. Unbounded Knapsack: 같은 물건을 여러 번 넣을 수 있음 (ex. 동전 문제)
3. Fractional Knapsack: 물건을 쪼개서 넣을 수 있음

이 문제는 1번에 해당한다.

 

코드

#include <iostream>
#include <vector>

using namespace std;

struct info {
    int w, v;
};

int knapsack(int n, int k, vector<info> &item) {
    vector<int> dp(k + 1, 0);

    for (int i = 0; i < n; i++) {
        for (int j = k; j >= item[i].w; j--)
            dp[j] = max(dp[j], dp[j - item[i].w] + item[i].v);
    }

    return dp[k];
}

int main() {
    int n, k;
    vector<info> item;

    // 입력
    cin >> n >> k;
    item.assign(n, {0, 0});
    for (int i = 0; i < n; i++)
        cin >> item[i].w >> item[i].v;

    // 출력
    cout << knapsack(n, k, item);

    return 0;
}