python 백준 12865 평범한 배낭

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

N,K = map(int,input().split())
backpack = [0]*(K+1)
for _ in range(N):
    W,V = map(int,input().split())
    for i in range(len(backpack))[::-1]:
        if backpack[i] and i + W <= K:
            backpack[i+W] = max(backpack[i+W],backpack[i]+V)
    if W <= K:
        backpack[W] = max(backpack[W],V)
print(max(backpack))

dp 활용

• backpack index = 무게, value = 최대 가치
• 순서에서 고생
  • backpack[W] = max(backpack[W],V)를 2중 포문보다 먼저 쓸 경우 같은 물건을 두번 쌓는 문제
  • for i in range(len(backpack))[::-1] 역순으로 하지 않으면 문제 발생
    • 물건으로 1,1 값이 두번 들어온다고 가정, backpack = [1,2,3,4,5,6,...] 으로 만들어짐