[C++] 백준 12865번 - 평범한 배낭 (knapsack) 문제

#골드5

 

 

백준 12865번 문제는 정말 유명한 알고리즘인 knapsack 알고리즘의 대표문제이다.

knapsack 알고리즘은 쪼갤 수 있냐 없냐에 따라 두 가지로 나뉘는데 만약 쪼갤 수 없다면, brute force와 dynamic programming으로 풀 수 있다.

 

그러나 brute force 방법은 시간복잡도가 O(2^n)만큼 잡아먹어서 n이 크다면 극악의 시간복잡도이다. 그래서 웬만한 ps에는 쓰이지 않을 것이다.

 

반면에 dp는 중첩 for문으로 이차원 배열을 사용하기 때문에 O(n^2)으로 쓸만하다.

 

추가적으로 만약 쪼갤 수 있는 knapsack 문제이면 greedy하게 해결도 가능하다.

이 방법은 다른 포스팅에서 다뤄보겠다.

 

문제 링크

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

12865번: 평범한 배낭

 

알고리즘

 

dynamic programming 기법으로 knapsack문제를 해결하였다.

value[i][j]는 2차원 배열로 i번째 물건까지 선택을 마친 무게 j에서 최대의 value를 가진 dp 테이블이다.

 

Item 구조체를 만들고, items라는 구조체 배열을 먼저 선언한다.

첫 번째 for문에서 i는 i 번째 입력받은 item에 대한 선택을 의미하고, j는 무게를 의미한다.

 

크게 두 가지 케이스로 나뉘는데, 현재 무게에 지금 선택된 것을 포함할 수 있는지, 없는지이다.

현재 선택할 item의 무게가 너무 커서 선택할 수 없다면 if(wi > j) 문 안을 돌게 된다.

 

만약 무게가 가능하다면, 두 가지 경우 중 max값을 찾아야 한다.

1. 지금 선택된 것을 포함 안하는게 나을지

2. 포함 하는 것이 나을지

 

1번의 경우, 포함을 안 하는 경우이기 때문에 바로 이전 단계의 value를 그대로 가지고 온다. value[i-1][j]

2번의 경우는 포함을 하는 경우이기 때문에 이것을 선택하기 전 단계(지금 무게에서 현재 아이템 무게를 빼면 됨) value[i-1][j-wi]에 현재 아이템 value인 vi를 더하면 된다. 

 

1,2번 중 더 높은 값을 찾아야 하기 때문에 max 함수를 이용하면 된다. 

 

 

코드

#include <iostream>

using namespace std;

struct Item{
    int weight, value;
};

int value[101][100001];
int n, k;
Item items[101]; 

int main()
{
    cin >> n >> k;
    for(auto i =1;i<=n;i++){
        int w, v;
        cin >> w >> v;
        items[i] = {w,v};
    }
    
    // knapsack dp
    for(auto i=1;i<=n;i++){
        for(auto j=1; j<=k; j++){
            int wi = items[i].weight;
            int vi = items[i].value;
            if(wi > j){ 
                // 현재 무게에 지금 선택된 것을 포함 x
                value[i][j] = value[i-1][j];
            }else{
                // 무게는 가능, 가치를 따짐.
                // 지금 선택된 것을 포함 X vs 포함 O
               value[i][j] = max(value[i-1][j], vi + value[i-1][j-wi]);
            }
            
        }
    }
    cout << value[n][k] << '\n';
    return 0;
}

 

 

제출 결과

for문 범위 잘못 선택해서 3트..!