0-1 knapsack1 [DP] Knapsack Problem (0-1 Knapsack) References Algorithms (Sanjoy Dasgupta) Contents Knapsack Problem (배낭 문제) with repetition without repetition Knapsack Problem 배낭 문제(knapsack problem)는 간단하게 다음과 같습니다. 한 여행가의 배낭에 담을 수 있는 무게의 최댓값(W)이 정해져 있습니다. 담을 수 있는 항목은 총 n개가 있는데, 이들의 무게는 \(w_1, \cdots, w_n\)이고, 그 항목의 가치는 \(v_1, \cdots, v_n\) 일 때, 가치의 합이 최대가 되도록 배낭에 담을 항목을 고르는 방법은 무엇일까요? 예를 들어, W = 10일 때를 생각해보도록 하겠습니다. 이 문제는 두 종류의 버전이 존재합니다. 만약 각.. 2022. 4. 14. 이전 1 다음
