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

문제

 

---

풀이

 

여러가지 풀이방법으로 풀 수 있는 냅색 문제이다. 이번엔 동적계획법으로 풀어야 한다.

 

특정 물건 i가 있다고 하자. 이 i에 대해 할 수 있는 것은 2가지이다. 배낭에 넣거나, 배낭에 넣지 않거나.

무조건 넣을 수 있는 것도 아니다. 버틸 수 있는 무게가 5인데 6짜리 물건은 넣을 수 없다.

그럼 어차피 못넣는 경우는 빼고, 넣을 수 있는 경우 이 물건을 넣어야 할까 말아야 할까?

 

1~N까지의 물건(i)과 1~K까지의 무게(j)가 있다고 하고 이걸 dp[i][j]라는 배열에 저장한다고 하자.

그니까 dp[2][4]라면 나에게 2개의 물건이 있고 4만큼의 무게를 들 수 있는 상황이라는 것이다.

 

dp[i][j]에 대해 물건을 넣지 않을 경우 dp[i][j] = dp[i-1][j]이다. 물건을 넣지 않았으니 무게가 변할리는 없고, i번째 물건까지 사용할 수 있으나 사용하지 않았으니 i-1번째까지의 물건이 있던 경우와 상황이 같은 것이다.

dp[i][j]에 대해 물건을 넣는 경우라면 dp[i][j] = value[i] + dp[i-1][j-W[i]]이다. 물건을 넣었으니 i번 물건의 가치인 value[i]가 더해질 것이고, i-1번째까지의 물건을 조회한 상황에서, W[j]만큼의 무게를 담을 공간은 필요하니 dp[i-1][j-W[j]]를 가져와야 한다.

 

그니까 이 두 경우 중 큰 값을 취하며 배열을 채우면 된다.

설명이 어려워 예제 입력1에 대한 표를 작성했다.

파란색은 N이고 초록색은 K다.

3열 3행의 값이 6인 것을 볼 수 있는데, 들 수 있는 무게가 3이고 보유하고 있는 물건이 1~3번째 물건일 때 들 수 있는 최댓값이다.

최종적으로 필요한 값은 4열 7행의 값이겠다.

---

소스코드

 

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

int W[101], V[101];
int dp[101][100001];

int knapsack(int N, int K) { //컴알 강의자료 참고함
    for (int i = 1; i <= N; i++) { //각 아이템에 대해
        for (int j = K; j >= 0; j--) { //모든 경우의 무게에 대해 계산해보는 것임
            if (W[i] > j)
                dp[i][j] = dp[i - 1][j];
            else
                dp[i][j] = max(dp[i - 1][j], V[i] + dp[i - 1][j - W[i]]);
        }
    }
    return dp[N][K];
}

int main() {
    int N, K;

    cin >> N >> K;
    for (int i = 1; i <= N; i++)
        cin >> W[i] >> V[i];
    cout << knapsack(N, K);
}

위에서 설명한 내용을 그대로 코드로 옮겼을 뿐이다.

난 사실 주로 dfs, bfs로 풀던 문제라 익숙하지만 낯선 문제였다.