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

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

12865번: 평범한 배낭

 

 

⭐ 문제

 

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

 

 

⭐ 코드 분석

 

가치 : 배낭에 넣은 물건이 최대 가치가 되도록

무게 : 처음 정했던 가방 최대 무게를 넘지 않도록

 

1. 배낭의 허용 무게 보다 넣을 물건의 무게가 크다면 넣지 않음
2. 나은 가치를 선택하여 배낭에 물건을 담음
 2-1. 현재 넣을 물건의 무게 만큼 배낭에서 빼기, 현재 물건을 넣음
 2-2. 현재 물건을 넣지 않고 이전 배낭 그대로 가지고 감

 

 

• i : 담을 물건의 인덱스
• j : 가방 허용 용량
• weight : 현재 담을 물건의 무게
• value : 가치

1. j < weight : d [ i ][ j ] = d [ i - 1 ][ j ]
2. d [ i ][ j ] = max ( d [ i - 1 ][ j - weight ] + value, d [ i - 1 ] [ j ] )

d 리스트에 배낭이 가지는 최대 가치가 저장

 

 

💥 냅색 알고리즘 : 배낭의 크기가 지정 되어 있을때 최대 무게를 계산하는 알고리즘

 

 

물건 1~4를 넣을 수 있는 경우

0 kg1 kg2 kg3 kg4 kg5 kg6 kg7 kg

X	0	0	0	0	0	0	0	0
물건 1 (6kg)	0	0	0	0	0	0	13	13
물건 2 (4kg)	0	0	0	0	8	8	13	13
물건 3 (3kg)	0	0	0	6	8	8	13	14
물건 4 (5kg)	0	0	0	6	8	12	13	14

 

위 표가 d 가 가지는 요소 이다

 

 

< 알고리즘 점화식 >

dp[i][j]=max(dp[i−1][j],dp[i−1][j−wi​]+vi​])
vi​: 물건의 가치wi​ : 물건의 무게dp[i][j] : 최대 이윤 (i : 현재 넣은 물건의 번호, j: 넣을 수 있는 최대 무게)

 

 

 

⭐ 코드

 

n, k = map(int, input().split())

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

for i in range(n):
    thing.append(list(map(int, input().split())))

for i in range(1, n+1):
    for j in range(1, k+1):
        w = thing[i][0]
        v = thing[i][1]

        if j < w:
            d[i][j] = d[i-1][j]
        else:
            d[i][j] = max(d[i-1][j], d[i-1][j-w]+v)

print(d[n][k])