[Python 파이썬]백준 12865번 - 평범한 배낭

2023년 5월 15일

문제 링크 : 12865번 - 평범한 배낭

문제

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

입력

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

출력

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

알고리즘 분류

• 다이나믹 프로그래밍
• 배낭 문제

---

문제 접근

대표적인 다이나믹 프로그래밍 문제이며, 정확히는 0-1 Knapsack 문제로 볼 수 있겠다.
배낭이 감당할 수 있는 무게가 주어졌을 때, 가방에 물건을 이것저것 넣어 가장 가치가 높을 때의 해당 가치를 출력하는 문제이다.
해당 문제는 아래 점화식을 활용하여 풀 수 있다.

wi = 현재 배낭에 넣어보려는 물건의 무게
vi = 현재 배낭에 넣어보려는 물건의 가치

i = 현재 넣어보려는 물건을 포함해 베낭에 넣을 총 물건의 개수
w = 배낭의 한계 무게를 가정한 값. w = 3이라면, 배낭의 한계무게가 3일 때 라고 가정한 것.

dp[i][w] = 배낭에 현재 넣을 물건을 포함 i개 넣으려 하고, 배낭 한계무게가 w라고 가정했을 때, 배낭에 담을 수 있는 최대 가치
           
i번째 물건을 한계무게가 w인 배낭에 넣으려고 할 때, 최대 가치를 구하고 싶다. (dp[i][w] 구하기)

'''
dp[i][w] 구하는 점화식
'''

if wi > w (넣으려는 물건의 무게가 배낭 한계무게보다 무겁다면 넣지못함) :
        dp[i][w] = dp[i-1][w] # 해당 물건을 넣기 전의 상태(가치)를 그대로 가져옴
                    
else(넣으려는 물건이 배낭에 들어갈 수 있다면 넣어보기위해 경우의 수를 따짐) :
        # 해당 물건을 넣을 공간을 창출해(w - wi), 해당 물건을 넣어본 상태의 가치를 합산.
        # 합산한 가치와, 해당 물건을 넣기 전의 상태(가치)를 비교하여 더 큰 값을 대입함.
        dp[i][w] = max(dp[i-1][w], dp[i-1][w - wi] + vi)

---

순서도

1. 물건의 무게 배열 weight, 물건의 가치 배열 price 선언

2. weight, value 배열에 각각 입력받는 물건의 정보를 기입(무게, 가치)

3. knapsack 함수 호출.
    3-1 dp 선언. size는 (K+1) x (N+1), 모든 요소는 0 로 초기화.
        3-1-1. dp의 행은 현재까지 넣은 물건의 개수
        3-1-2. dp의 열은 현재 배낭의 무게 상태
        3-1-3. dp[행][열]은 현재까지 넣은 물건들의 최대 가치 합
        
    3-2. dp[1][1]부터 수행, 0행과 0열은 무시하고 진행해야 한다.
        3-2-1. 0행은 물건을 0개 넣는다는 뜻으로, 0행 요소는 모두 0으로 둠
        3-2-2. 0열은 베낭의 한도 무게가 0이라는 뜻으로, 아무것도 못 넣으니 모두 0으로 둠
        
    3-3. 점화식을 이용해 모든 dp[i][w]를 구한다.
    
4. 마지막 dp 요소를 출력한다.

 

---

입력 예제

4 7
6 13
4 8
3 6
5 12

각 물건의 무게와 가치 쌍을 구분하여 배열에 담아둔다. 그림은 각각 사이즈를 물건의 개수만큼 선언했지만, 0번째 인덱스에 더미 값이 있다고 가정하자. 실제 코드도 그렇게 구현하였다.
만약 2번째 물건을 배낭에 넣어보려 시도하면, 2번째 물건의 무게 wi = W[2], 가치 vi = V[2]를 통해 알아낼 수 있을 것이다.
그리고 다이나믹 프로그래밍 기법을 사용하기 위해, 2차원 배열인 dp를 선언해준다. 사이즈는 (물건의 개수 + 1) X (배낭의 한계무게 + 1), 0번째 행과 0번째 열은 모두 0으로 초기화 시켜준다. (실제 코드에선 그냥 선언할 때부터 모두 0으로 초기화했다.)
 
점화식에 근거하여, 1번째 행을 채워보자. 이는 1번째 물건을 배낭에 넣으려고 시도할 때를 뜻한다.

1번째 물건의 wi = 6, vi = 13이다.dp[1][1~5] 는 모두 w가 1~5로 wi보다 작다. 이는 아래 점화식에 의해 다음과 같이 수행된다.

if wi > w (넣으려는 물건의 무게가 배낭 한계무게보다 무겁다면 넣지못함) :
            dp[i][w] = dp[i-1][w] # 해당 물건을 넣기 전의 상태(가치)를 그대로 가져옴

dp[1][1~5]는 dp[0][1~5] 요소를 각각 대입한다.
 
dp[1][6~7]은 wi <= w를 충족한다. wi <= w의 의미는, 1번째 물건을 배낭에 넣을 수 있다는 뜻이다. 이는 아래 점화식에 의해 다음과 같이 수행된다.

else(넣으려는 물건이 배낭에 들어갈 수 있다면 넣어보기위해 경우의 수를 따짐) :
                # 해당 물건을 넣을 공간을 창출해(w - wi), 해당 물건을 넣어본 상태의 가치를 합산.
                # 합산한 가치와, 해당 물건을 넣기 전의 상태(가치)를 비교하여 더 큰 값을 대입함.
                dp[i][w] = max(dp[i-1][w], dp[i-1][w - wi] + vi)

dp[1][6] = max(dp[0][6], dp[0][0] + 13) = max(0, 13) = 13
dp[1][7] = max(dp[0][7], dp[0][1] + 13) = max(0, 13) = 13
 
해당 방식과 같이 2번째 행까지 채웠다 가정하고, 3번째 행으로 넘어가보자.

점화식를 이용해 다음과 같이 각 요소를 정의할 수 있을 것이다.

• dp[3][1~2] : wi > w 이므로, dp[2][1~2] 값을 각각 대입한다.
• dp[3][3~7] : wi <= w 이므로, max(dp[2][3~7], dp[2][3~7 - wi] + vi)를 각각 대입한다.

dp[3][7] 값을 찾아보자. wi <= w 이므로, 3번째 물건을 넣을 수 있는 상태이다. 3번째 물건까지 배낭에 넣고 싶은데, 배낭의 한계무게가 7이라고 가정했을 때 최대 가치는 무엇인가? 를 담을 위치이다.
해당 위치에 들어갈 값은, 다음 두 값을 비교했을 때 더 큰 값이다.

• dp[2][7] : 3번째 물건을 넣지 않고, 2번째 물건까지 넣었을 때의 가치
• dp[2][7 - wi] + vi = dp[2][4] + 6 = 2번째 물건까지 넣은 경우의 수 중, 3번째 물건을 넣기 위한 공간을 확보한 이후, 3번째 물건을 넣었을 때의 최종 가치

dp[2][7]은 13, dp[2][4] + 6 = 14로 14가 대입될 것이다.
이 비교를 굳이 문장으로 풀어보면 다음과 같다.

• 2번째 물건을 넣는 경우의 수 중, 3번째 물건을 넣기 위해 공간을 확보하여 3번째 물건을 넣었을 때 가치가, 3번째 물건을 넣지 않고 2번째 물건까지 넣었을 때의 가치보다 더 높은 것이다.

그리고 나머지 줄을 모두 채우면 다음과 같이 dp가 채워진다.

dp[ i ][ w ]	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	13	13
2	0	0	0	0	8	8	13	13
3	0	0	0	6	8	8	13	14
4	0	0	0	6	12	12	13	14

최종적으로, 물건 4개를 한계무게가 7인 배낭안에 "어떤 조합"으로든 넣었을 때의 최대 가치는 dp의 마지막 요소에 담길 것이다. dp의 마지막 요소인 dp[4][7]을 출력하면 원하는 답이 도출된다.

출력 예제

14

---

주의할 점

• 0-1 Knapsack 문제가 이해가 안된다면, 직접 손으로 표를 작성하고 점화식에 맞춰 표를 채워보는게 도움이 된다고 생각한다. 이해하고 익숙해져 내 것으로 만드는 것이 중요하다.

 

---

전체 코드

# 12865

def knapsack(N,K):
    global weight, value
    dp = [[0 for _ in range(K+1)] for _ in range(N+1)]
    for i in range(1,N+1):
        wi = weight[i] # wi : 현재 베낭에 넣어보려는 물건의 무게
        vi = value[i] # vi : 현재 베낭에 넣어보려는 물건의 가치
        for w in range(1,K+1):
            if wi > w: # 현재 넣으려는 물건을 넣을 수 없다면, 위쪽 값을 dp[i][w]에 삽입
                dp[i][w] = dp[i-1][w]
            
            # 현재 베낭 상태에, 넣으려는 물건을 넣을 수 있다면
            # max(왼쪽, 베낭에 있는 물건 개수 -1 (i - 1)인 상태에서, 물건 무게 wi를 뺀 상태에서 최대 가치 + 새로넣을 물건의 가치 v1)
            else: 
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - wi] + vi)
                
    print(dp[N][K])


if __name__ == "__main__":
    N,K = map(int,input().split())
    weight = [-1]
    value = [-1]
    
    for _ in range(N):
        W,V = map(int,input().split())
        weight.append(W)
        value.append(V)

    knapsack(N,K)

 

---

풀이 후기

알고리즘 수업 때, 0-1 Knapsack 문제를 직접 손으로 표를 작성해보며 답을 도출하는 과제를 수행한 적이 있는데, 확실히 도움이 되는 과제였고, 오랜만에 0-1 냅색문제를 접해도 크게 어렵지 않게 풀 수 있었다.