[Python] 백준 12865. 평범한 배낭

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

12865번: 평범한 배낭

Knapsack Problem으로 유명한 문제, DP의 대표적인 유형이라고 한다.

 

 

상세한 문제 풀이는 이곳에서 볼 수 있다.

https://huiyu.tistory.com/entry/DP-01-Knapsack%EB%B0%B0%EB%82%AD-%EB%AC%B8%EC%A0%9C

[DP] 0/1 Knapsack(배낭) 문제

 

	import sys
	N, K = map(int, sys.stdin.readline().split())
	result = [[0 for _ in range(K+1)] for _ in range(N)]
	for i in range(N):
	weight, value = map(int, sys.stdin.readline().split())
	for idx in range(1, K+1):
	if idx >= weight:
	result[i][idx] = max(result[i-1][idx], result[i-1][idx - weight] + value)
	else:
	result[i][idx] = result[i-1][idx]
	print(max(result[-1]))

view raw [백준] 평범한 배낭.py hosted with ❤ by GitHub