아이디어는 Greedy 접근법이 Fractional Knapsack 문제에 대한 최상의 솔루션을 제공한다는 사실을 구현하는 것입니다.
특정 노드가 더 나은 솔루션을 제공할 수 있는지 여부를 확인하기 위해 Greedy 접근 방식을 구현하는 최적의 솔루션(노드를 통해)을 계산합니다. Greedy 접근법 자체로 계산된 솔루션이 지금까지 최고 이상이라면 노드를 통해 더 나은 솔루션을 얻을 수 없습니다.
완전한 알고리즘은 아래와 같습니다 -
-
Greedy Approach를 구현하여 상한값을 계산할 수 있도록 단위 중량당 값의 비율이 내림차순으로 모든 항목을 정렬합니다.
-
maxProfit =0과 같은 최대 이익 초기화
-
빈 대기열 Q가 생성됩니다.
-
의사결정 트리의 더미 노드를 생성하여 Q에 삽입하거나 큐에 넣습니다. 더미 노드의 이익과 가중치는 0이 됩니다.
-
Q가 비어 있지 않거나 비어 있지 않은 동안 다음을 수행하십시오.
-
Q에서 항목이 생성됩니다. 추출된 항목을 u로 둡니다.
-
다음 레벨 노드의 이익을 계산합니다. 이익이 maxProfit보다 크면 maxProfit을 수정합니다.
-
다음 레벨 노드의 경계를 계산합니다. bound가 maxProfit보다 높으면 Q에 다음 레벨 노드를 추가합니다.
-
다음 레벨 노드가 솔루션의 일부로 취급되지 않거나 고려되지 않는 경우를 고려하고 다음 레벨로 큐에 노드를 추가하지만 다음 레벨 노드를 처리하거나 고려하지 않고 가중치와 이익을 얻습니다.
-
아래에 제공된 그림 -
입력
// First thing in every pair is treated as weight of item
// and second thing is treated as value of item
Item arr1[] = {{2, 40}, {3.14, 50}, {1.98, 100}, {5, 95}, {3, 30}};
Knapsack Capacity W1 = 10
출력
The maximum possible profit = 235