[Baekjoon 12856] 평범한 배낭

문제 12856

Knapsack algorithm

• Fractional Knapsack Problem: 담을 수 있는 물건이 나누어질 수 있을 때
• 0-1 Knapsack Problem: 담을 수 있는 물건이 나누어질 수 없을 때
  추후 공부할 예정

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
stuff = [[0,0]]
knapsack = [[0 for _ in range(K+1)] for _ in range(N+1)] 

for _ in range(N):
    stuff.append(list(map(int, input().split())))

for i in range(1, N + 1):
    # 현재 물건
    weight, value = stuff[i]
    for j in range(1, K + 1):
        # 가방에 담을 수 없는 경우
        if j < weight:
            knapsack[i][j] = knapsack[i - 1][j] 
        # 가방에 담을 수 있다면 현재 가치 + 현재 무게를 뺀 가치 값과 이전 가치 값 중 최대값
        else:
            knapsack[i][j] = max(value + knapsack[i - 1][j - weight], knapsack[i - 1][j])

print(knapsack[N][K])

풀이

1. 가방 무게(K), 물건 개수(N) 만큼의 배열 생성
2. 물건을 차례대로 돌며 다음과 같은 알고리즘 수행
   3-1. 현재 물건을 넣고 남은 무게를 채울 수 있는 최댓값을 위 행에서 가져와 더함
   3-2. 현재 물건을 넣을 수 없으면 이전 물건들로 채우는 값을 가져옴
3. 3-1, 3-2 중 더 큰 값을 저장. 즉, 현재까지의 물건들로 구성할 수 있는 가장 가치 높은 구성
4. knapsack[N][K]는 K 무게일 때의 최댓값을 의미

결과

참고
1차원 배열 방식