문제 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 풀이 DP의 유형 중에서도 배낭 문제(Knapsack)의 대표 문제이다. 해당 유형의 문제를 풀기 전에는 배낭 알고리즘을 공부하고 풀어보는 것을 추천한다. 배낭 알고리즘은 여러 물건 중에서 특정한 조건을 만족시키는 조합을 구하는 문제들에 적용이 가능하다. 위의 문제에서 우리는 물건들 중에서 최대 무게를 넘지 않는 가치의 최댓값..