[백준]평범한 배낭

12865번: 평범한 배낭

이 문제는 유명한 냅색 알고리즘 이다.

냅색(Knapsack: 배낭) 알고리즘이란 담을 수 있는 물건이 나눌수 있냐 없냐에 따라 나눈다.

담을 수 있는 물건이 나누어 질 때(설탕 몇 g등) : 분할 가능 배낭문제

담을 수 있는 물건이 나누어 질 수 없을 때(담는다 or 안담는다): 0-1 배낭문제이다.

 

냅색 알고리즘은 문제를 보면 생각나는 방법은 두가지정도이다.

1. 모든 경우의 수를 넣어본다. -> 너무무느릴거 같으며 범위가 너무 높다. (대략 1억이 넘을 거 같음)

2. 그리디로 풀 생각을 해보자 -> 담을 수 있는 물건이 큰 물건에서 나누어지지 않는다.

3. DP 확정

 

알고리즘

1. x 축엔 가방 1~k 까지의 무게, y 축은 물건 N개 개수 만큼의 배열을 만들어준다.

2. 행을 차례대로 돌며 다음과 같은 알고리즘을 수행한다.

1. 현재 물건이 현재 돌고 있는 무게보다 작다면 [이전물건][같은무게]([i-1][j])를 입력해준다.
2. 현재 물건을 넣어준다. 물건을 넣은 뒤에 남은 무게를 채울 수 있는 최댓값([i-1][j-weight])을 위의 행에서 가져와 더해준다.
3. 현재 물건을 넣어주는 것보다, 다른 물건들로 채우는 값([i-1][j-weight])을 가져온다.
4. 1과 2 중 더 큰 값을 [i][j]에 저장해준다. 이값은 현재까지의 물건들로 구성할 수 있는 가장 가치 높은 구성이다.
5. [N][K]는 곧, K무게일 떄의 최댓값을 가리킨다.

import sys
input = sys.stdin.readline
N, bag = map(int, input().split())
arr = [(0,0)]
for i in range(N):
    a, b = map(int,input().split())
    arr.append((a,b))

map = [list(range(bag+1)) for _ in range(N+1)]

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

        if j < weight:
            # weight가 현재 들수 있는 값보다 작으면 위에 것 (현재를 뺀 전의 가치)을 가져온다.
            map[i][j] = map[i-1][j]
        else:
            # (현재 가치 + 현재를 제외한 가치들 중에 무게를 뺸것) , (현재를 뺀 전의 가치)
            map[i][j] = max(value + map[i-1][j-weight], map[i-1][j])

print(map[N][bag])