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

코딩 코딩 코오딩 2022. 2. 26. 17:19

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

12865번: 평범한 배낭

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)

www.acmicpc.net

이 문제는 다이나믹프로그래밍으로 메모지에이션을 활용해서 푼 방법인다.

이문제를 풀기위해 나는 결국에는...? 못풀었지만 다른 분들의 풀이를 참고하며 풀었다

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

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

https://www.acmicpc.net/problem/12865 #Solution https://huiyu.tistory.com/entry/DP-01-Knapsack%EB%B0%B0%EB%82%AD-%EB%AC%B8%EC%A0%9C 참조하였음. 유명한 냅색 문제, 냅색 알고리즘이다. 간단하게 말하면..

claude-u.tistory.com

이분의 풀이를 전적으로 참고했다. 유명한 알고리즘 인가보다.

n, k = map(int, input().split())
stuff = [[0,0]]
bag = [[0]*(k+1) for i in range(n+1)]
for i in range(n):
    w, v = map(int, input().split())
    stuff.append((w,v))

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:
            bag[i][j] = bag[i - 1][j]
        else:
            bag[i][j] = max(value + bag[i - 1][j - weight], bag[i - 1][j])
        
print(bag[n][k])