백준 12865 - 평범한 배낭

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

12865번: 평범한 배낭

전형적인 DP 문제입니다.

import sys
N,K= map(int,sys.stdin.readline().split())	#입출력 
result=[[0 for _ in range(K+1)]for _ in range(N)]	#허용할수 있는 K의 가치의 범위
for i in range(N):	
    weight,value=map(int,sys.stdin.readline().split())	#입출력
    for idx in range(1,K+1):	#K를 범위에 포함
        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]))	#가장 마지막 어레이의 최대값 출력

KEYPOINT

---

1. 배낭에 하나씩 넣는다.

2. 새로운 아이템이 배낭에 들어갈때 새로운 아이템을 넣을때의 가치와 기존의 아이템을 유지할때의 가치를 비교한다.

3. 가치판단에 따라 순차적으로 모든 아이템을 배낭에 담을때의 최대의 가치를 측정하고 갱신한다.

4. 마지막 배열(모두 넣어보고 판단한 경우)의 최대값을 return 한다.

 

배낭 상황표 참조:https://huiyu.tistory.com/entry/DP-01-Knapsack%EB%B0%B0%EB%82%AD-%EB%AC%B8%EC%A0%9C