[Algorithm] 가방문제(냅색 알고리즘, knapsack algorithm)

 

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

 

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

 

#. Solve

 

dp[j] 는 가방에 담을 수 있는 무게의 한계

j 는 보석의 최대 가치라고 해보자.

 

dp[3] 이라면 보석의 최대 가치는 3인 것이고,

dp[5] 라면 보석의 최대 가치는 5일 것이다.

 

Knapsack Algorithm도 DP유형이므로

작은 문제의 해를 구하면서 큰 문제의 해를 구해낼 수 있다.

바로 Memorization을 활용해서!

 

입력이

4 11 (보석 종류의 개수, 가방에 담을 수 있는 무게의 한계값)

5 12 (무게, 가치)

3 8

6 14

4 8

로 주어질 때,

 

dp의 초기값은 아래와 같다.

무게의 한계값은 11kg이므로 11kg까지 넣을 수 있는만큼 보석을 넣어보는 것이다.

각 인덱스는 무게의 한계를 의미하고, 값은 가치를 의미한다.

 

 

먼저 5 12 를 적용해보면 아래 그림처럼 된다.

5kg 에 12의 가치를 가진 보석.

j가 0~4일 경우, 5kg의 보석을 넣을 수 없으므로, pass해준다.

여기서  "dp[i] = dp[j-무게] + 가치"  가 성립하게 되는데

j =5,

가방 가치가 0[한계 0kg]인 상태에서 5kg 무게의 보석을 넣으면 +12의 가치를 얻을 수 있다.

j = 6,

마찬가지로 가방 가치가 0[한계 1kg]인 상태에서 5kg 무게의 보석을 넣으면 +12의 가치를 얻을 수 있다.

j = 7,

마찬가지로 가방 가치가 0[한계 2kg]인 상태에서 5kg 무게의 보석을 넣으면 +12의 가치를 얻을 수 있다.

j = 8,

마찬가지로 가방 가치가 0[한계 3kg]인 상태에서 5kg 무게의 보석을 넣으면 +12의 가치를 얻을 수 있다.

j = 9,

마찬가지로 가방 가치가 0[한계 4kg]인 상태에서 5kg 무게의 보석을 넣으면 +12의 가치를 얻을 수 있다.

j = 10,

이번에는 가방 가치가 12[한계 5kg]인 상태에서 5kg 무게의 보석을 넣으면 +12의 가치를 얻을 수 있다.

j = 11,

이번에도 가방 가치가 12[한계 6kg]인 상태에서 5kg 무게의 보석을 넣으면 +12의 가치를 얻을 수 있다.

 

 

다음으로 3 8 를 적용해보자.

3kg 에 8의 가치를 가진 보석.

j가 0~2일 경우, 3kg의 보석을 넣을 수 없으므로, pass해준다.

"dp[i] = dp[j-무게] + 가치"

j =3,

가방 가치가 0[한계 0kg]인 상태에서 3kg 무게의 보석을 넣으면 +8의 가치를 얻을 수 있다.

j =4,

가방 가치가 0[한계 1kg]인 상태에서 3kg 무게의 보석을 넣으면 +8의 가치를 얻을 수 있다.

j =5,

가방 가치가 0[한계 2kg]인 상태에서 3kg 무게의 보석을 넣으면 +8의 가치를 얻을 수 있다.

하지만 이미 12라는 더 높은 가치를 가지고 있기 떄문에 pass

5kg을 넣을 수 있을 때, 3kg, 8가치를 넣는 것보다 5kg, 12가치를 넣는 것이 더 이득이니깐

j =6,

가방 가치가 8[한계 3kg]인 상태에서 3kg 무게의 보석을 넣으면 +8의 가치를 얻을 수 있다.

기존 가치인 12보다 더 높은 16을 저장

6kg을 넣을 수 있을 때, 5kg, 12가치를 넣는 것보다 3kg x 2, 16 가치를 넣는 것이 더 이득

j =7,

가방 가치가 8[한계 4kg]인 상태에서 3kg 무게의 보석을 넣으면 +8의 가치를 얻을 수 있다.

j =8,

가방 가치가 12[한계 5kg]인 상태에서 3kg 무게의 보석을 넣으면 +8의 가치를 얻을 수 있다.

기존 12에서 20으로 수정

...

j =11,

가방 가치가 20[한계 8kg]인 상태에서 3kg 무게의 보석을 넣으면 +8의 가치를 얻을 수 있다.

기존 24에서 28로 수정

 

이러한 동작으로 반복하면서 

가방에 담을 수 있는 보석의 최대가치를 구할 수 있다.

 

+ 2021.03.15

*

다차원 배열의 Memorization을 활용한다면,

이전 값에 변동이 없기 때문에 정방향으로 보석을 넣어보아도 괜찮지만

 

일차원 배열의 Memorization은 이전 값이 계속해서 변하게 된다.

 

일차원 Memorization에서 보석을 정방향으로 넣다보면

이전 값을 참조하는 dp[j-w] + v 식에서 

이미 넣은 보석을 또 넣어보게되는 상황이 발생할 수 있다.

 

코린이 시절... 강의를 보면서 복습겸 작성한 글인데 엄청난 오류가 있었다..

발견해주신 sad, 안녕하세요님께 감사드립니다.!

 

#. Code

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
int main(void)
{
    int N, M, w, v, i, j;
    scanf("%d %d", &N, &M);
    vector<int> dp(M + 1);
 
    for (i = 0; i < N; i++) {
        scanf("%d %d", &w, &v);
 
        for (j = M; j >= w; j--)
            dp[j] = max(dp[j], dp[j - w] + v);
    }
 
    printf("%d\n", dp[M]);
 
    return 0;
}

line 12~17) 모든 보석을 하나씩 넣어보자

line 15) 뒤에서부터(가방에 담을 수 있는 무게의 최댓값)부터 보석을 넣어보자.

           (정방향으로 넣게 되면 dp[j-w]+v 에서 무게가 중첩되는 경우가 발생)

line 25) 가방 무게의 한계에 따른 최대 가치는 기존 최대 가치와 해당 보석을 넣었을 때 중 max

          (해당 보석을 넣기 전 무게를 확보하기 위해 무게의 한계에서 보석의 무게를 뺀다고 생각)

 

 

#. Result

  - Input --------------------------------------------------------

4 11

5 12

3 8

6 14

4 8

------------------------------------------------------------------

 

  - Output --------------------------------------------------------

26

------------------------------------------------------------------