12865번: 평범한 배낭
이 문제 하나로 설명되는 알고리즘…!
얼핏 보기에는 무게 대비 최대 가치를 갖는 물건부터 넣으면 된다고
생각할 수 있으나… (그리디식 접근)
가방에 담을 수 있는 무게가 확실하게 정해져 있으므로
만약 무게 3에 가치 100인 물건이 있더라 하더라도 무게 1에 가치 1인 물건을
담아야 하는 불가피한 상황이 생길 수 있다…!
→ 2차원 dp로 해결 가능하다..!!