0-1Knapsack

배낭 문제 (Knapsack Problem) 물건 n개 각 물건 i, 무게 wi, 가치 vi 배낭 용량 C 위 조건에서 배낭에 담을 수 있는 물건의 최대 가치를 찾는 문제 단, 배낭에 담을 물건의 무게 합이 C를 초과하지 않고 각 물건은 1개씩만 존재 이러한 문제를 0-1 배낭이라고 명칭 부분 문제 K[i, w] 물건의 1 ~ i 까지만 고려하고, 배낭의 용량이 w일 때의 최대 가치 최적해 - K[n, C] C의 값이 매우 크면 알고리즘 수행시간이 매우 길어짐 Pseudo code Knapsack Input 배낭의 용량 C n개의 물건 각 물건 i의 무게 w 와 가치 v Output - K[n, C] 1. for i = 0 to n K[i, 0] = 0 // 배낭의 용량이 0일 때 2. for w = 0..