[백준] 12865 평범한 배낭 파이썬

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

12865번: 평범한 배낭

 

 

https://www.youtube.com/watch?v=rhda6lR5kyQ

냅색문제 제대로 풀어본 적이 없어 위 링크에서 공부했다.

 

a, k = map(int, input().split())

stuff = [(0, 0)]
for i in range(1, a+1):
    stuff.append(tuple(map(int, input().split())))

knapsack = [[0] + [-1]*k for _ in range(a+1)]
knapsack[0] = [0] * (k+1)

# 탑다운
def maxVal(n, w):
    if n == 0 or w == 0:
        return knapsack[n][w]
    if knapsack[n][w] != -1:
        return knapsack[n][w]
    if w < stuff[n][0]: # 넣을 수 있는 무게보다 현재 물건이 무거울 때
        knapsack[n][w] = maxVal(n-1, w)
        return knapsack[n][w]

    knapsack[n][w] = max(maxVal(n-1, w-stuff[n][0]) + stuff[n][1], maxVal(n-1, w))
    return knapsack[n][w]

print(maxVal(a, k))

w를 k로 써서 계속 틀렸었다...... 이상하게 예시는 다 맞아서 찾는데 엄청 오래 걸렸다.

탑다운 방식으로 먼저 구현하고, 바텀탑 방식으로도 구현해보려고 했는데

에너지 다 써서 포기

 

아래 글이 바텀업방식이다.

https://claude-u.tistory.com/208

#159 백준 파이썬 [12865] 평범한 배낭 - 냅색 알고리즘

 

+) 2022.02.08

새로 풀어봤다

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
things = [list(map(int, input().split())) for _ in range(n)]

knapsack = [[0]*(k+1) for _ in range(n+1)]

for i in range(1, n+1): #물건
    wei, val = things[i-1][0], things[i-1][1]
    for j in range(1, k+1): #무게
        if j >= wei:
            knapsack[i][j] = max(knapsack[i-1][j], knapsack[i-1][j-wei]+val)
        else:
            knapsack[i][j] = knapsack[i-1][j]

print(*knapsack, sep="\n")
print(knapsack[n][k])

위 글에서 참고했다