Program for fractional knapsack problem

                            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;

Output:

Conclusion:

Thus we successfully perform the program to implement fractional

knapsack problem.