백준 12865 : 평범한 배낭 (파이썬)

import sys
N, K = map(int, sys.stdin.readline().split())
dp = [[0] * (K + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
    w, v = map(int, sys.stdin.readline().split())
    for j in range(1, K + 1):
        if j >= w: # 1
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v) # 2
        else: # 3
            dp[i][j] = dp[i - 1][j] # 4
print(dp[N][K])

 

코드를 보면서 적어놓는게 나중에 더 이해가 쉬울 것 같아서 코드블럭을 앞으로 빼 두었다.

 

1. 만약 현재 내가 들 수 있는 무게가 j 일 때 넣으려는 물건의 무게 w 까지 충분히 들 수 있다면,
2. 이전 것만 넣고 현상유지 할 것인지, 이전것을 유지하면서 지금것도 넣을건지 결정한다. 왜냐하면 무게 제한이 있기 때문에 가치가 같을 때 되도록이면 안 넣는게 유리하기 때문이다.
   • 이전 것을 넣는데 오히려 w 를 빼는 이유 :
     1. 여유 공간이 j 라는 어떤 양 인데 거기서 w 만큼을 뺀다 == w 만큼 넣었다고 가정하는것이다.
     2. 왜 넣었는데 + 가 아니고 - 를 쓸까?
     3. 여유 공간에 어떤 물건을 넣었으니, 여유 공간 j 에서 넣은 물건의 양 만큼인 w 를 빼는것이다.
     4. 즉 j - w 는 j 에 w 만큼 넣었을 때 남은 공간
     5. j + w 라는 계산을 하게 되면 배낭에 원래 w 가 있던 상태에서 w 를 도로 빼버린다는 의미이다.
     6. 저 부분을 한글로 풀어서 정리하면...
        • max(
          현상 유지, w 만큼을 더 넣은 무게일 때의 가치 + 지금 물건의 가치
          )
        • 위는 결국 현상 유지를 할 것인지, dp[j - w] 만큼의 여유가 있었을 때 했던 최선의 선택에 지금 물건의 가치를 합친 것과 비교한다는 의미이다.
3. 남은 여유 무게가 j 인데 넣으려는 물건의 무게 w 가 그를 넘어버린다면,
4. 더 이상 공간이 없으므로 현상 유지밖에 방법이 없다.