In This post we have write a c program to implement fractional knapsack problem Algorithm for subject of Analysis of Algorithms | Computer Engineering | Mumbai University (MU) | (Semester 4)
Knapsack problem is also called as rucksack problem. In Knapsack problem, given a set items with values and weights and a limited weight bag . We have to find the optimum solution so that, in minimum cost(value) fill the bag with the maximum weight.
Program:
#include <stdio.h>
#include<conio.h>
void main()
{
int capacity, no_items, cur_weight, item;
int used[10];
float total_profit;
int i;
int weight[10];
int value[10];
printf("Enter the capacity of knapsack:\n");
scanf("%d", &capacity);
printf("Enter the number of items:\n");
scanf("%d", &no_items);
printf("Enter the weight and value of %d item:\n", no_items);
for (i = 0; i < no_items; i++)
{
printf("Weight[%d]:\t", i);
scanf("%d", &weight[i]);
printf("Value[%d]:\t", i);
scanf("%d", &value[i]);
}
for (i = 0; i < no_items; ++i)
used[i] = 0;
cur_weight = capacity;
while (cur_weight > 0)
{
item = -1;
for (i = 0; i < no_items; ++i)
if ((used[i] == 0) &&
((item == -1) || ((float) value[i] / weight[i] > (float)
value[item] / weight[item])))
item = i;
0 Comments