[Code Tree] 배낭 채우기 [Python]

문제

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-knapsack/description

배낭 채우기 설명 | 코드트리

 

---

풀이

문제 요약

N개의 보석 중 무게가 M이 넘지 않도록 적절히 골라 최대 값어치를 만드는 냅색 문제다.

아이디어

대표적인 냅색 문제다. N개의 보석에 대해 최대 무게 M ~ 현재 보석의 무게 W[i]에 대한 최댓값을 구해주자.

for i in range(N):
    for m in range(M, w[i] - 1, -1):
        dp[m] = max(dp[m], dp[m - w[i]] + v[i])

print(dp[M])

풀이 시간

5분

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/code-tree/Trail-4-Intermediate-Low/DP I/25 배낭 채우기(challenge-knapsack).py

problem-solving/code-tree/Trail-4-Intermediate-Low/DP I/25 배낭 채우기(challenge-knapsack).py at main · rogi-rogi/problem-