Knapsack Problem (Python)

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

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)가 주어진다.

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

출력

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

예제 입력 1

4 7
6 13
4 8
3 6
5 12

예제 출력 1

14

 

위 문제를 풀다가 모르겠어서 찾아보니 Knapsack 알고리즘에 대해서 알게되었다. 공부 겸 기록을 남긴다.

 

---

Knapsack Problem

배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정한 가치의 무게가 정해진 짐들을 배낭에 담을 때, 가치의 합이 최대가 되는 조합을 찾는 알고리즘

Fractional Knapsack Problem

물건을 쪼갤 수 있는 배낭 문제로, 가치가 높은 순으로 정렬한 뒤 배낭에 담고, 텍스트남은 부분은 물건을 쪼개어 넣어 조합을 찾을 수 있음. 그리디 알고리즘으로 해결 가능

Knapsack Problem

물건을 쪼갤 수 없는 배낭 문제로, 동적계획법(Dynamic Programming)을 활용해 해결 가능

 

---

문제 해결 과정

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

가방에 넣을 수 있는 최대 무게가 7kg일 때, 최대 가치는 얼마인지 구하라

 

물건을 넣었을 때 무게 별 최대 가치를 나타내는 2차원 dp 테이블을 만들어준다.

 

1. 물건을 넣지 않았을 때

	0kg	1kg	2kg	3kg	4kg	5kg	6kg	7kg
x	0	0	0	0	0	0	0	0
1 (6kg,13)
2(4kg,8)
3(3kg,6)
4(5kg,12)

 

2. 물건1 만 넣었을 때

	0kg	1kg	2kg	3kg	4kg	5kg	6kg	7kg
x	0	0	0	0	0	0	0	0
1 (6kg,13)	0	0	0	0	0	0	13	13
2(4kg,8)
3(3kg,6)
4(5kg,12)

물건 1은 6kg이므로 6kg이후에는 물건 1의 가치 13이 들어간다.

 

3. 물건1,2 만 넣었을 때

	0kg	1kg	2kg	3kg	4kg	5kg	6kg	7kg
x	0	0	0	0	0	0	0	0
1 (6kg,13)	0	0	0	0	0	0	13	13
2(4kg,8)	0	0	0	0	8	8	13	13
3(3kg,6)
4(5kg,12)

물건 2의 무게는 4kg이므로 4,5kg은 물건 2의 가치 8이 들어가고 6kg부터는 물건 1과 물건 2 둘 다 가능하지만 둘 중 가치가 더 큰 물건 1의 13이 들어간다

 

4. 물건1,2,3 만 넣었을 때

	0kg	1kg	2kg	3kg	4kg	5kg	6kg	7kg
x	0	0	0	0	0	0	0	0
1 (6kg,13)	0	0	0	0	0	0	13	13
2(4kg,8)	0	0	0	0	8	8	13	13
3(3kg,6)	0	0	0	6	8	8	13	14
4(5kg,12)

7kg의 경우에는 물건 1이 들어가는 경우, 물건 2,3이 같이 들어가는 경우가 있는데 이 경우 물건 2,3이 같이 들어가는 가치가 14로 더 크므로 14가 들어간다.

 

5. 물건1,2,3,4 넣었을 때

	0kg	1kg	2kg	3kg	4kg	5kg	6kg	7kg
x	0	0	0	0	0	0	0	0
1 (6kg,13)	0	0	0	0	0	0	13	13
2(4kg,8)	0	0	0	0	8	8	13	13
3(3kg,6)	0	0	0	6	8	8	13	14
4(5kg,12)	0	0	0	6	8	12	13	14

5kg의 경우 물건 4의 가치 12가 더 크므로 12가 들어간다.

 

위 과정을 점화식으로 표현하면

$$ d[i][j] = max(d[i-1][j],d[i-1][j-w_i]+v_i)$$
$$ v_i : 물건의 가치 $$
$$ w_i : 물건의 무게 $$
$$ d[i][j] : 최대 이윤(i : 현재 넣은 물건의 번호, j : 넣을 수 있는 최대 무게) $$

 

위 문제를 코드로 구현하면

# 물품의 수 n
# 버틸 수 있는 무게 k
n, k = map(int,input().split())

arr = [[0,0]]

for _ in range(n):
    # w : 물건의 무게
    # v : 가치
    w,v = map(int,input().split())
    arr.append([w,v])

d = [[0]*(k+1) for _ in range(n+1)]

for i in range(1,n+1):
    for j in range(1,k+1):
        weight = arr[i][0]
        value = arr[i][1]

        # 가방에 넣을 수 없으면
        if j < weight:
            # 위의 값 그대로 가져오기
            d[i][j] = d[i-1][j]
        # 가방에 넣을 수 있다면
        else:
            d[i][j] = max(d[i-1][j],d[i-1][j-weight] + value)

print(d[n][k])