반응형 greedy1 Greedy greedy make the choice that appears best at each moments 주어진 문제를 부분 문제로 쪼갰을 때 부분 문제의 상태에서 선택할 수 있는 최선의 선택을 고름 그 앞까지의 결과와 앞으로의 결과를 고려하지 않은 선택 개략적인 접근 방법 기준에 따른 Sorting ⇒ 기준을 무엇으로 정할 것인가? 가장 앞의 것을 고름 The Fractional Knapsack Problem n개의 item 각각의 item은 weight와 profit이 존재 weight의 합이 W가 넘지 않도록 item을 고를 때, profit의 합이 최대가 되는 item subset? 이때 item을 ratio r만큼 “부분” 가져올 수 있다. greedy approach item들을 “profits .. 2022. 12. 9. 이전 1 다음 728x90