[Python] 백준12865 평범한 배낭

26 May 2023 in Study on Algorithm

백준12865 평범한 배낭 링크

문제

예제 입력

---

코드

import sys

n, m = map(int, input().split())
arr = [[0,0]] + [ list(map(int, sys.stdin.readline().split())) for _ in range(n)]

dp = [[0]*(m+1) for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1, m+1): 
            if arr[i][0] <= j:       
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-arr[i][0]]+arr[i][1])
            else : 
                dp[i][j] = dp[i-1][j]
         
print(dp[-1][-1])

설명

파이썬을 통해서 사용자로부터 입력받아 dp알고리즘을 사용하여 평범한 배낭를 정복 분할하여 구현했습니다.

---

결과