Like us on google+

Wednesday, 21 May 2014

Widgets

Knapsack Problem Solved Using Greedy Approach.

#include <stdio.h>
main()
{
int i, n, j, cap;
printf("Enter the number of items:");
scanf("%d",&n);
double a[n][4];
for(i=0; i <n; i++)
{
printf("Item %d:\n",i+1);
printf("Enter weight and value:");
scanf("%lf",&a[i][0]);
scanf("%lf",&a[i][1]);
a[i][2]=(double)a[i][1]/a[i][0];
a[i][3]=i+1;
}
printf("Enter capacity of knapsack:");
scanf("%d",&cap);


printf("before sorting\n");
printf("weight\t\tvalue\t\tval/weight\titemno\n ------------------------------------------\n");
for(i=0;i<n;i++){
for(j=0;j<n;j++){
printf("%f\t",a[i][j]);
}
printf("\n");
}
double temp1,temp2,temp3,temp4;
for(i=1;i<n;i++) // bubble sort
{
for(j=0;j<n-i;j++)
{
if(a[j][2]>a[j+1][2])
{
temp1=a[j][0];
temp2=a[j][1];
temp3=a[j][2];
temp4=a[j][3];

a[j][0]=a[j+1][0];
a[j][1]=a[j+1][1];
a[j][2]=a[j+1][2];
a[j][3]=a[j+1][3];

a[j+1][0]=temp1;
a[j+1][1]=temp2;
a[j+1][2]=temp3;
a[j+1][3]=temp4;

}
}


}
printf("after sorting the rows based on value/weight in increasing order\n");
for(i=0; i<n; i++)
{
printf("%6.2lf%6.2lf%6.2lf%6.2lf",a[i][0],a[i][1],a[i][2],a[i][3]);
printf("\n");
}
i = n-1;
int val=0;
while(cap>0&&i>=0)
{
if(a[i][0]<=cap)
{
printf("Put item %lf in the knapsack.\n", a[i][3]);
cap-=a[i][0];
val=val+a[i][1];
}
i--;
}
printf("\nTotal value included is %d.\n", val);
}
----------------------------------------------------------------------------------------------------------
OUTPUT:
Enter the number of items:4
Item 1:
Enter weight and value:2
12
Item 2:
Enter weight and value:1
10
Item 3:
Enter weight and value:3
20
Item 4:
Enter weight and value:2
15
Enter capacity of knapsack:5
before sorting
weight value val/weight itemno
 -------------------------------------------------------------------------
2.000000       12.000000         6.000000        1
1.000000       10.000000        10.000000       2
3.000000       20.000000        6.666667        3
2.000000       15.000000        7.500000        4
after sorting the rows based on value/weight in increasing order
  2.00 12.00  6.00  1.00
  3.00 20.00  6.67  3.00
  2.00 15.00  7.50  4.00
  1.00 10.00 10.00  2.00
Put item 2 in the knapsack.
Put item 4 in the knapsack.
Put item 1 in the knapsack.

Total value included is 37.

SHARE THIS POST   

  • Facebook
  • Twitter
  • Myspace
  • Google Buzz
  • Reddit
  • Stumnleupon
  • Delicious
  • Digg
  • Technorati
About us:
Hi guys Sandesh and Rajesh here ... studing engineering in PESIT started this blog as a google contest and also we love blogging ...Hope u like it ...Encourage us by liking us on g+... Any queries dont hesitate to ask Read More →

0 comments: