Scribd
Upload
19 views2 pages

Lab7 Knapsack Greedy

This C program implements a greedy algorithm to solve the knapsack problem. It takes user input for the number of items, their weights, and profits, then calculates the maximum profit that can be obtained given a specified capacity. The program sorts items based on their profit-to-weight ratio and accumulates the total value until the knapsack is full.

Uploaded by

lavanyas
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
19 views2 pages

Lab7 Knapsack Greedy

This C program implements a greedy algorithm to solve the knapsack problem. It takes user input for the number of items, their weights, and profits, then calculates the maximum profit that can be obtained given a specified capacity. The program sorts items based on their profit-to-weight ratio and accumulates the total value until the knapsack is full.

Uploaded by

lavanyas
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

#include<stdio.

h>

int main()

float weight[50],profit[50],ratio[50],Totalvalue,temp,capacity,amount;

int n,i,j;

printf("Enter the number of items :");

scanf("%d",&n);

for (i = 0; i < n; i++)

printf("Enter Weight and Profit for item[%d] :\n",i);

scanf("%f %f", &weight[i], &profit[i]);

printf("Enter the capacity of knapsack :\n");

scanf("%f",&capacity);

for(i=0;i<n;i++)

ratio[i]=profit[i]/weight[i];

for (i = 0; i < n; i++)

for (j = i + 1; j < n; j++)

if (ratio[i] < ratio[j])

temp = ratio[j];
ratio[j] = ratio[i];
ratio[i] = temp;

temp = weight[j];
weight[j] = weight[i];
weight[i] = temp;

temp = profit[j];
profit[j] = profit[i];
profit[i] = temp;
}

printf("Knapsack problems using Greedy Algorithm:\n");

for (i = 0; i < n; i++)


{

if (weight[i] > capacity)

break;

else

Totalvalue = Totalvalue + profit[i];

capacity = capacity - weight[i];

if (i < n)

Totalvalue = Totalvalue + (ratio[i]*capacity);

printf("\nThe maximum value is :%f\n",Totalvalue);

return 0;

You might also like