(DP) 백준 12865번 _ 평범한 배낭 [Python]

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

12865번: 평범한 배낭

12865번 문제 : 평범한 배낭

이 문제는 DP문제(냅색문제)다.

 

처음에는 DP(다이나믹 프로그래밍)의 개념을 생각하지 않은 채 그냥 생각나는대로 코드를 적었다.

대부분의 테스트 케이스에서 맞췄지만, 아래에서 나오는 (4,6), (4,2), (4,10) 과 같이 같은 무게이면서 value가 여러개인 test case는 통과하지 못했다.

# my answer (wrong)
N, K = map(int,input().split())
data = []
for i in range(N):
    data.append(tuple(map(int,input().split())))
data.sort(key=lambda x:x[0])
answer = []
def my_value(data):
    status = 0
    for j in range(len(data)):
        value = 0
        w = 0
        for i in data[j:]:
            if w+i[0] > K:
                answer.append(value)
                status = 1
                break
            else:
                w += i[0]
                value += i[1]
        if status == 0:
            answer.append(value)
my_value(data)

print(max(answer))

 

DP 로직을 생각하면서 표로 이차원 배열을 그려가며 해결하면 다음과 같다.

DP 로직의 핵심은 크게 두가지다.

1. 재귀적으로 생각하기

2. 불필요한 계산 줄이기

 

위 사항을 고려해서 코드를 짜보면 다음과 같다.

# answer
import sys

N, K = map(int, input().split())
stuff = [[0,0]]
knapsack = [[0 for _ in range(K + 1)] for _ in range(N + 1)]

for _ in range(N):
    stuff.append(list(map(int, input().split())))


for i in range(1, N + 1):
    for j in range(1, K + 1):
        weight = stuff[i][0] 
        value = stuff[i][1]
       
        if j < weight:
            knapsack[i][j] = knapsack[i - 1][j] #weight보다 작으면 위의 값을 그대로 가져온다
        else:
            knapsack[i][j] = max(value + knapsack[i - 1][j - weight], knapsack[i - 1][j])

print(knapsack[N][K])

 

냅색 및 DP와 관련된 다른 문제들을 더 많이 풀어봐야겠다.

 

아직은 로직을 완벽하게 구현하지는 못하는 것 같다.