[백준] 12865번: 평범한 배낭 - python

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

12865번: 평범한 배낭

 

냅색 알고리즘 응용문제 

n, m = map(int, input().split())

dp = [0] * (m+1)
for _ in range(n):
    w, v = map(int, input().split())

    # 역순으로 루프를 돌며 최대 가치 계산
    for j in range(m, w-1, -1):
        dp[j] = max(dp[j], dp[j-w]+v)

# 최종 결과 출력
print(dp[m])

이 코드는 각 물건을 한 번씩만 고려하면서, 가능한 모든 무게 조합에 대해 최대 가치합을 계산. 이를 통해 무게 m까지의 배낭에 담을 수 있는 최대 가치 계산할 수 있당

 

완성