[python] 백준 - 12865. 평범한 배낭

🤔문제 해결

• G5 | DP, 냅색 알고리즘(배낭 알고리즘)

딱 봐도 너무 복잡해 보이는 DP... 2차원 배열로 풀어야할 것 같다.

행은 각 아이템, 열은 현재 무게(?)

1. 아이템 하나를 고른다.
2. 가방의 버틸 수 있는 무게를 0부터 M까지 올려본다.
3. 해당 무게별로 최대로 채울 수 있는 가장 큰 값을 채운다.

사실 그렇게 딱!!! 완전히 이해는 하지 못했다... 역시 DP는 어려움

나중에 비슷한 문제를 한번 더 풀면 이해가 가지 않을까...

 

💻소스 코드

import sys

input = sys.stdin.readline
N, M = map(int, input().split())  # 물품 수, 최대 무게
items = [tuple(map(int, input().split())) for _ in range(N)]
# print(items)

dp = [[0] * (M + 1) for _ in range(N + 1)]
# for row in dp:
#     print(row)
# print()

for item_idx in range(1, N + 1):
    for weight in range(1, M + 1):
        item_weight, item_value = items[item_idx - 1]
        
        # 계산단계의 무게가 물건의 무게보다 작아서 아직 해당 단계의 물건을 못넣음
        if weight < item_weight:
            dp[item_idx][weight] = dp[item_idx - 1][weight]
        else:
            dp[item_idx][weight] = max(dp[item_idx - 1][weight], dp[item_idx - 1][weight - item_weight] + item_value)

        # for row in dp:
        #     print(row)
        # print()

print(dp[-1][-1])

 

📕문제 확인

출처: BACKJOON ONLINE JUDGE

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

12865번: 평범한 배낭