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