기록하는 개발자

짐 싸기 문제(가방에 물건을 담는 케이스)는 동적 계획법으로 해결할 수 있는 경우가 많습니다. 여러 물건이 있을 때, 특정한 조건을 만족하는 조합을 구하는 문제입니다. 대표적인 문제로는 백준 12865 평범한 배낭 문제가 있습니다. 물건의 무게(W)와 가치(V)가 주어지고, 담을 수 있는 배낭의 최대 무게가 주어집니다. 이 때 베낭에 넣을 수 있는 물건들의 최대 가치를 구하는 문제입니다. 해당 냅색문제에서는 물건을 쪼갤 수 없다고 가정합니다. 해당 문제에서 물건의 개수가 N = 4개이고, 베낭의 최대 용량은 K = 7입니다. 1번째 물건 2번째 물건 3번째 물건 4번째 물건 W(무게) 6 4 3 5 V(가치) 13 8 6 12 dp[i][j] = 첫 번째 물건부터 i번째 물건까지 살펴봤을 때, 베낭의 용..