[1Day 1Algo] 백준 12865번 평범한 배낭 (C++)

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

 

알고리즘 개요

냅색(Knapsack) 알고리즘

 : 배낭의 용량이 정해져 있을 때, 최대한의 가치 를 갖도록 배낭을 싼다.

   주어진 물건들의 용량과 가치를 고려하여 담을지 말지 결정한다.

 

풀이 과정

Example)

물건의 수(N) = 4, 배낭의 용량(K) = 7

물건	물건 1	물건 2	물건 3	물건 4
무게	6	4	3	5
가치	13	8	6	12

1) 각각의 물건에 대한 최대 가치를 판별할 수 있도록 DP[K] 를 만든다.

 

2) 물건을 넣을지 말지의 경우를 모두 저장하며 구한다.

    a) 현재 배낭의 허용 무게보다 넣을 물건의 무게가 더 크다면 넣지 않는다.

 

    b) 그렇지 않다면, 다음 중 더 나은 가치를 선택하여 넣는다.

         DP[j] = max((DP[j-현재 물건 무게]+현재 물건 가치), DP[j])

 

        b-1) 현재 넣을 물건의 무게만큼 배낭에서 뺀다.
                그리고 현재 물건을 넣는다.

                 DP[j] = DP[j-현재 물건 무게] + 현재 물건 가치

        b-2) 현재 물건을 넣지않고, 이전 배낭 그대로 가지고 간다.
                 DP[j]=DP[j]

 

3) 마지막 아이템까지 DP를 진행하면, 가방 무게가 k일때의 d[k]값이 최대한의 가치를 갖는다.

 

* DP를 2차원 배열에 저장하면 훨씬 직관적이다. 그러나 메모리와 시간을 위해 1차원 배열을 사용하였다.

* 1차원 배열을 사용하면, 배열을 갱신할 때 뒤에서부터 갱신해야한다. 그래야 이전 값들을 사용할 수 있기 때문이다.

 

DP Flow

DP[j] = max((DP[j-현재 물건 무게]+현재 물건 가치), DP[j])

DP[7] = max((DP[7-6]+13), DP[7])
         = max(13, 0)

DP[6] = max((DP[6-6]+13), DP[6])
         = max(13, 0)

 

DP[j] = max((DP[j-현재 물건 무게]+현재 물건 가치), DP[j])

DP[7] = max((DP[7-4]+8), DP[7])
         = max(8, 13)

DP[6] = max((DP[6-4]+8), DP[6])
         = max(8, 13)

DP[5] = max((DP[5-4]+8), DP[5])
         = max(8, 0)

DP[4] = max((DP[4-4]+8), DP[4])
         = max(8, 0)

 

 

DP[j] = max((DP[j-현재 물건 무게]+현재 물건 가치), DP[j])

DP[7] = max((DP[7-3]+6), DP[7])
         = max(14, 13)

DP[6] = max((DP[6-3]+6), DP[6])
         = max(6, 13)

DP[5] = max((DP[5-3]+6), DP[5])
         = max(6, 8)

DP[4] = max((DP[4-3]+6), DP[4])
         = max(6, 8)

DP[3] = max((DP[3-3]+6), DP[3])
         = max(6, 0)

 

DP[j] = max((DP[j-현재 물건 무게]+현재 물건 가치), DP[j])

DP[7] = max((DP[7-5]+12), DP[7])
         = max(12, 14)

DP[6] = max((DP[6-5]+12), DP[6])
         = max(12, 13)

DP[5] = max((DP[5-5]+12), DP[5])
         = max(12, 8)

 

 

Code

#include <iostream>
using namespace std;
int w[101], v[101], dp[100001];

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

    cout << dp[k];
    return 0;
}

 

참고 블로그

https://hongcoding.tistory.com/50

https://gumeum.tistory.com/25

https://wlshddlek.tistory.com/67