백준 12865 평범한 배낭 - 파이썬 풀이 🦄

• 백준 12865 평범한 배낭 - 파이썬 풀이 🦄
  • 문제
  • Keypoints
  • Solution
  • References

백준 12865 평범한 배낭 - 파이썬 풀이 🦄

문제

DP를 이용해서, sob problem에 대한 해를 활용하는 문제이다.

Keypoints

• Bigger problem : 주어진 N개의 물건에 대해서 모든 무게 W에 대한 가치를 최대화 한다.
• Smaller problem : 주어진 N-1개의 물건에 대해서 모든 무게 W에 대한 가치를 최대화 한다.
• 따라서 모든 무게에 대해서 가치의 최대값을 저장하고 새로운 물건(W, V)을 추가하면서 업데이트 하면 된다.

Solution

from sys import stdin as stdin   

N, MAXIMUM_VALUE = map(int, stdin.readline().strip().split())
dp = [0 for i in range(MAXIMUM_VALUE+1)]

weights = []
for i in range(N):
    weight, value = map(int,  stdin.readline().strip().split())
    dp[weight] = value  
    weights.append(weight)

weights.sort()
for i in weights:
    for j in weights:
        if i-j>0:
            dp[i] = max(dp[i], dp[j]+dp[i-j])

print(dp[MAXIMUM_VALUE])

References

Problem Link