[c++] 백준 12865 평범한 배낭 (배낭 문제 / Knapsack Problem)

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

문제 풀이법 : 배낭 알고리즘으로 해결

- 배낭 문제

어떤 배낭이 있고, 그 안에 넣을 수 있는 최대무게가 k가 있다. 배낭에 넣을 수 있는 n개의 물건은 각기 다른 가치 v를 가지고있고, 다른 무게 w를 가지고 있을 때, 배낭이 최대한 가치가 높은 물건들을 담을 수 있는 조합을 찾는 문제

-Dynamic Programming

Brute Force로 풀 수 있겠지만 시간복잡도가 O(2^n)으로 상당히 비효율적이다.
그래서 이 문제는 DP문제이다 ^____^

-solution

우리는 2개의 점화식을 만들 수 있다.
b배열 : 무게를 저장하기위한 DP배열
k : 현재 넣을 물건의 번호
wk : k번째 물건의 무게
W : 가방의 최대무게(제한무게)

---

배낭문제 해설

1. b[k][W] = b[k-1][W], if wk>W

배낭에 물건을 넣을 때 우리는 두가지 경우 물건을 넣기 / 넣지 않기​ 를 선택 할 수 있다.

현제 넣으려는 무게가 가방의 제한무게를 초과한다면, 넣지 않기 밖에 선택 할 수 없다.

위 식은, k번째 물건이 무게를 초과한 경우, 최대가치를 k-1번째 물건을 넣을 경우의 가치로 정하는것이다.

2. b[k][W] = max(b[k-1][W], b[k][W-wk] + val(wk))

만약 물건을 넣을 수 있는 무게가 조금이라도 남았을때! 우리는 두가지 경우를 선택 할 수 있다.

새로운 물건을 넣지않기 / 현재 물건을 빼고 공간을 만들어서 새로운 물건을 넣기

우리는 두 경우 중 더 큰 값을 선택해야한다. 그것이 위 식이다.

b배열 채우는 방법

예시를 들어 가방을 채워보자.

---

4종류의 물건이 있다.

1 - 2kg / $3
2 - 3kg / $4
3 - 4kg / $5
4 - 5kg / $6

가방의 최대 무게는 5kg이다.

아오 벨로그 table로 만들고 싶었는데 별로라서 이전에 만들었던 표를 사진으로 첨부한다.

시작 배열이다. 물건이 없거나 무게가 0인경우는 모두 0이다.

먼저 1번 물건만 생각을 해보자. b[1][2] 의 경우 1번물건을 하나 넣을 수 있으니 b[1][2]=3 이다. 1번 보석만 생각하는 경우이므로 더이상 넣을게 없으니 오른쪽 칸들도 전부 3이다.

이제 1번 물건과 2번물건을 생각해보자. 무게가 2인 경우에는 3kg인 2번 물건을 넣을 수 없으므로 3이다. b[2][3]에서는 1번물건과 2번 물건을 둘 다 넣을 수 있다. 그 중 가치가 더 높은 2번 물건을 넣는 경우를 선택하여 b[2][3]=4이다.

그리고 b[2][5] 같은 경우는 1번 2번 물건을 모두 넣을 수 있으므로 b[2][5]=7이다.

최종 마지막칸에는 7이 들어간다. 이 마지막칸의 값이 최대한의 가치, 정답이다.

dp배열 채우는 코드

나는 vector와 pair을 이용해서 물건들의 값을 저장했다

    for(int i=1; i<=n; i++){
        for(int j=1; j<=k; j++){
            int fnt = v[i].first; //무게
            int sec = v[i].second; //가치
            
            if (fnt <= j){ //최대무게 이하
                if ((sec + b[i-1][j-fnt]) > b[i-1][j])
                    b[i][j] = sec + b[i-1][j-fnt];
                else
                    b[i][j] = b[i-1][j];
            }
            else //최대무게 초과
                b[i][j] = b[i-1][j];
        }
    }

전체코드

#include <iostream>
#include <vector>
using namespace std;

vector <pair<int,int>> v;
int n,k,b[105][100005]={0,};

int main(int argc, const char * argv[]) {
    
    cin>>n>>k;
    
    v.push_back({0,0});
    for (int i=0; i<n; i++){
        int x,y;
        cin>>x>>y;
        v.push_back({x,y});
    }
    
    for(int i=1; i<=n; i++){
        for(int j=1; j<=k; j++){
            int fnt = v[i].first; //무게
            int sec = v[i].second; //가치
            
            if (fnt <= j){ //최대무게 이하
                if ((sec + b[i-1][j-fnt]) > b[i-1][j])
                    b[i][j] = sec + b[i-1][j-fnt];
                else
                    b[i][j] = b[i-1][j];
            }
            else //최대무게 초과
                b[i][j] = b[i-1][j];
        }
    }
    
    cout<<b[n][k];
    
    return 0;
}