백준: 12865 평범한 배낭

문제

12865번: 평범한 배낭

 

문제 풀이

• 리스트를 만들 때, list[선택하고자 하는 아이템의 수][최대 가치]로 2차원 배열을 만든다.
• list[0]은 아무것도 연주하지 않은 상태, 최초에 볼륨을 적용한 상태이므로 list[0]의 값들은 0이다.
• 2중 반복문을 순회하면서 list[1], list[2] ... 로 접근하며 가방에 넣을 수 있는 아이템의 상태를 기록한다.
• n * m 만큼의 반복문을 순회하면, 최대 값어치을 체크한다.
• 즉, 이전에 선택한 아이템의 값어치를 유지하면서, 현재 선택한 아이템을 담았을 때의 상태를 반영한다.
  • 아이템을 담을 수 있는가?, 값어치는 이전과 비교하여 어느것을 선택하는게 최대값인가?
• 따라서 점화식은 그림과 같이, 현재 아이템을 가방에 넣을 수 있는 경우에 해당 아이템의 값어치를 반영하는가? 아닌가에 따라 최대값을 계산할 수 있다.

 

 

코드

from sys import stdin


if __name__ == "__main__":
    n, k = map(int, stdin.readline().split())
    items = [[0, 0]] + [list(map(int, stdin.readline().split())) for _ in range(n)]
    dp = [[0] * (k + 1) for _ in range(n + 1)]

    for idx in range(1, n + 1):
        weight, value = items[idx]
        for bag_weight in range(1, k + 1):
            if bag_weight < weight:
                dp[idx][bag_weight] = dp[idx - 1][bag_weight]
            else:
                dp[idx][bag_weight] = \
                    max(dp[idx - 1][bag_weight - weight] + value, dp[idx - 1][bag_weight])

    print(dp[n][k])