분수 배낭 문제

항목 목록이 제공되며 각 항목에는 고유한 가치와 무게가 있습니다. 아이템은 최대 무게 제한이 W인 배낭에 넣을 수 있습니다. 문제는 W보다 작거나 같은 무게를 찾아 값을 최대화하는 것입니다.

배낭 문제에는 두 가지 유형이 있습니다.

• 0 – 1 배낭
• 프랙셔널 배낭

0 – 1 배낭의 경우 항목을 더 작은 조각으로 나눌 수 없으며, 분수 배낭의 경우 항목을 더 작은 조각으로 나눌 수 있습니다.

여기서 우리는 분수 배낭 문제에 대해 논의할 것입니다.

이 알고리즘의 시간 복잡도는 O(n Log n)입니다.

입력 및 출력

입력:최대 가중치 =50. 값과 가중치가 있는 항목 목록.{(60, 10), (100, 20), (120, 30)}출력:최대 값:240가중치 20 및 30

알고리즘

fractionalKnapsack(무게, itemList, n)

입력 - 배낭의 최대 무게, 항목 목록 및 항목 수

출력: 얻은 최대값입니다.

값과 무게의 비율을 기준으로 항목 목록 정렬 시작 currentWeight :=0 knapsackVal :=목록의 모든 항목 i do if currentWeight + weight of item[i]  
예
 
#include #includeusing namespace std;struct item { int value, weight;};bool cmp(struct item a, struct item b) { // 가치와 가중치의 비율 double aRatio =(double)a.value / a.weight; 이중 bRatio =(이중)b.value / b.weight; return aRatio> bRatio;} double fractionalKnapsack(int weight, item itemList[], int n) { sort(itemList, itemList + n, cmp); //비교 함수를 사용하여 항목 목록 정렬 int currWeight =0; // 배낭의 현재 무게 double knapsackVal =0.0; for (int i =0; i  
출력
 
최대값:240