12865 평범한 배낭 문제 바로가기
접근방식
- 아마 알고리즘 수업들으시면서 교수님이 도둑이 문제 훔칠 때 보따리의 꽉 채우면서도 비싼 물건들을 고르는 방법! 이러시면서 설명하셨을 냅색 문제이다.
- 11053 가장 긴 증가하는 부분 수열의 알고리즘 형태로 풀고싶었으나 냅색 매트리스라는 새로운 변수가 꼭 필요한 문제였다.
- 9251 LCS와 비슷한 흐름의 문제인 것같다.
- 아래 블로그를 참고하였고 친절하게 설명해놓으셔서 아래 블로그글을 참고하는 것이 이해에 빠를 것 같다.
https://suri78.tistory.com/2
파이썬 코드
import sys
n, k = map(int, sys.stdin.readline().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])
참고
https://suri78.tistory.com/2
