Let us consider that there are n items in a store. The weight of item i is wi (where wi > 0) and the worth of the item is vi (where vi > 0). A thief has a knapsack by which he can carry some items of maximum weight of W pounds. In this problem the thief can carry a fraction xi of item i, where 0 ≤ xi ≤ 1. So, item i contributes xi.wi to the total weight in the knapsack, and xi. vi to the profit.
Hence, the objective function of the fraction knapsack problem can be written as follow:
maximize Σni=1 xi.vi subject to constraint Σni=1 xi.wi ≤ W
In this problem, the optimal solution can be achieved if the knapsack is full when the cumulative weight of the items is greater than the size of the knapsack. Thus in an optimal solution Σni=1xi.wi = W.
Greedy-fractional-knapsack (w, v, W)
FOR i = 1 to n
do x[i] = 0
weight = 0
while weight < W
do
i = best among remaining items
IF weight + w[i] <= W
then
x[i] = 1
weight = weight + w[i]
else
x[i] = (w - weight) / w[i]
weight = W
return x
Analysis
To solve this problem, first, we are sorting those elements. The sorting takes O(n log n) time. Selection of the items one by one is performed using a while loop, which takes O(n). Therefore, the complexity of the algorithm is O(n log n).
Implementation in C Language
#include<stdio.h>
#include<stdlib.h>
typedef struct weights_items{
int weight;
int profits;
}woi;
typedef struct knapsack{
woi *items;
float *ratio;
int s;
}knap;
void bubble_sort(knap *k);
int knapsack_using_greedy_method(knap *k, int capacity);
int main()
{
int size, capacity, i;
knap *k;
scanf("%d", &capacity);
scanf("%d", &size);
k = (knap *)malloc(sizeof(knap));
k->items = (woi*)malloc(size * sizeof(woi));
k->ratio = (float *)malloc(size * (sizeof(float)));
k->s = size;
for(i = 0; i < size; i++)
scanf("%d", &k->items[i].profits);
for(i = 0; i < size; i++)
scanf("%d", &k->items[i].weight);
for(i = 0; i < size; i++)
k->ratio[i] = (float)(k->items[i].profits) / (float)(k->items[i].weight);
bubble_sort(k);
printf(" %d ", knapsack_using_greedy_method(k, capacity));
return 0;
}
void bubble_sort(knap *k)
{
int i, j, s;
float t;
s = k->s;
woi temp;
for(i = 0; i < s; i++)
for(j = 0; j < s - i - 1; j++)
if(k->ratio[j] < k->ratio[j + 1] ){
temp = k->items[j];
k->items[j] = k->items[j + 1];
k->items[j + 1] = temp;
t = k->ratio[j];
k->ratio[j] = k->ratio[j + 1];
k->ratio[j + 1] = t;
}
}
int knapsack_using_greedy_method(knap *k, int capacity)
{
int max_profit=0,i=0;
for(i = 0; i < k->s; i++)
{
if(capacity >= k->items[i].weight)
{
max_profit += k->items[i].profits;
capacity -= k->items[i].weight;
}
else
{
max_profit += k->items[i].profits * ((float)(capacity) / (float)(k->items[i].weight));
break;
}
}
return max_profit;
}
Posts
No comments:
Post a Comment