백준 12865 - 평범한 배낭

문제

알고리즘 분류)

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

냅색(knapsack) 알고리즘 이라 불리는 문제이다
물건의 무게와 가치가 주어졌을 때 주어진 무게안에서 최대한의 가치를 담아야 한다

풀이

무게(가로) * 물건 갯수(세로) 만큼의 2차원 배열을 만들고
반복문으로 1행씩 해당 인덱스에 해당 무게일때의 최대 가치를 저장해나가며 배열을 완성한다

• 경우1) 현재담으려는 물건을 담았을 때 무게(w) 가 최대배낭무게를 넘어선다면 담지않는다
• 경우2) 현재담으려는 물건을 담는게 가능하다면
  • 2-1) 현재담으려는 물건만큼의 무게를 빼고 현재물건을 담는다
  • 2-2) 담지 않고 이전물건의 최댓값을 그대로 가져간다

중 큰 값을 선택하여야 한다

표로 살펴보면

3번째 물건을 탐색하는 경우 무게7에서
이전무게를그대로 가져오는 값(13) 보다 현재물건만큼의 무게를 빼고 현재물건을 담은 값(8+6)이 더 큰경우가 발생했다
이러한 식으로 표를 채워나가면
결국 배열[n,k] 에는 해당 무게일 때의 최대 가치가 저장되어 있는 것이다

소스코드

python)

import sys
N, K = map(int, input().split())
array = [[0 for col in range(K+1)] for row in range(N+1)]
bag = [[0,0]]

for _ in range(N):
    bag.append(list(map(int,sys.stdin.readline().split())))

for i in range(1,N+1):
    for j in range(1,K+1):
        if bag[i][0] > j:
            array[i][j] = array[i-1][j]
        else:
            array[i][j] = max(array[i-1][j-bag[i][0]]+bag[i][1], array[i-1][j])

print(array[-1][-1])