백준 12865 평범한 배낭

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

12865번: 평범한 배낭

DP에서 중요하다고 생각되는 내용 중 하나인 배낭 문제이다.

 

import sys

N, K = map(int, sys.stdin.readline().split())
dp = [[0] * (K + 1) for i in range(N + 1)]
thing = [[0, 0]]

for i in range(N):
    thing.append(list(map(int, sys.stdin.readline().split())))

for i in range(1, N + 1):
    w = thing[i][0]
    v = thing[i][1]
    for t in range(1, K + 1):
        if t < w:
            dp[i][t] = max(dp[i-1][t], dp[i][t-1])
        else:
            dp[i][t] = max(dp[i-1][t], dp[i][t-1],dp[i-1][t-w] + v)



print(dp[-1][-1])

옛날에 풀었던 코드이다.

 

너무 오래 전이라 기억도 안나고, 이번 주 과제이기 때문에 다시 풀어보도록 했다.

 

우선 DP 답게 기억할 배열이 필요하다.

범위는 무게인 0부터 W까지이다.

 

이제는 후보들을 반복문으로 돌면서 넣을지 말지를 판단해야 한다.

해당 짐이 들어갈 수 있는 모든 구간에 대해서, 현재 넣을 후보와 이 짐을 넣었을 때의 가치를 비교하고 무엇을 넣을지를 결정하면 된다.

import sys

N, K = map(int, sys.stdin.readline().split())

candidate_weight = []
candidate_value = []

for i in range(N):
    W, V = map(int, sys.stdin.readline().split())
    candidate_weight.append(W)
    candidate_value.append(V)

result = [0 for i in range(K + 1)]

for i in range(N):
    for t in range(candidate_weight[i], K + 1):
        result[t] = max(result[t], result[t-candidate_weight[i]] + candidate_value[i])

print(result[-1])

그래서 당연히 아무 생각없이 이렇게 코드를 만들었었다.

 

당연히 에러가 발생한다.

만약 가능한 무게가 8이고 4인 짐을 넣으려고 하면

[0, 0, 0, 0, 4, 0, 0, 0, 8] 이렇게 하나의 짐이 2번 들어가기 때문에 안쪽에 있는 반복문은 증가하는 방향이 아니라 감소하는 방향으로 만들어주어야 한다.

 

import sys

N, K = map(int, sys.stdin.readline().split())

candidate_weight = []
candidate_value = []

for i in range(N):
    W, V = map(int, sys.stdin.readline().split())
    candidate_weight.append(W)
    candidate_value.append(V)

result = [0 for i in range(K + 1)]

for i in range(N):
    for t in range(K, candidate_weight[i] - 1, -1):
        result[t] = max(result[t], result[t-candidate_weight[i]] + candidate_value[i])

print(max(result))