[백준][Python][12865][DP]평범한 배낭

문제 : https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

0-1 Knapsack 문제다.

 

이 문제는 진짜 기본중에 기본이고 다른 DP는 잘만풀면서 맨날 이것만 나오면 틀리길래 각잡고 푼다.

 

0-1 Knapsack 문제는 가방 무게 K 한도 내에서 최대한 비싼 물건들을 챙겨나오는 문제다.

 

중요한 점은 다음과 같다.

DP [물건 1-i 번째 까지 ] [ 현재 배낭의 무게 j ]

• 가방의 현재 가능한 무게 > 현재 물건의 무게 면 못들고 나가니까 그냥 가야한다
  • dp[아이템 i][무게 j] = dp[아이템 i-1][무게 j]
• 가방의 현재 가능한 무게 <= 현재 물건의 무게 면 들고 갈 수 있는데
  
  • 과연 i 번째 물건을 들고 가면 다음 물건 포기하고도 이득일까?
  • dp[아이템 i][무게 j] = min( dp[아이템 i-1][무게 j], dp[아이템 i-1][무게 j - 현재아이템 i 무게 ] + 현재 아이템 i 의 가치 )
  • i번째 물건 까지 본 결과 = min( 현재 아이템을 안먹고 그대로 가는 경우 , 현재 아이템 을 먹고가는 경우  )

 

import sys

n,k = [int(i) for i in sys.stdin.readline().split()]

item = []
dp = [[0]*(k+1) for _ in range(n)]

for _ in range(n):
    item.append([int(i) for i in sys.stdin.readline().split()])


for i in range(n):
    for j in range(1,k+1):
        if item[i][0]>j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max( dp[i-1][j], dp[i-1][j-item[i][0]] + item[i][1])


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