KnapSack Problem Program:
class KnapSack
{
static int i[]={1,2,3,4,5,6};
static int w[]={2,3,1,5,3,2};
static int v[]={6,4,3,7,5,4};
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
System.out.println("Enter KnapSack Size");
int size=sc.nextInt();
float temp[]=new float[i.length];
float sum=0;
for(int x=0;x<=i.length-1;x++)
{
temp[x]=(float)v[x]/w[x];
}
insertion_sort(temp);
for(int x=0;x<=i.length-1;x++)
{
if(size >= w[x])
{
sum=sum+v[x];
size=size-w[x];
}
else
{
sum=sum+(v[x]*(float)size/w[x]);
size=0;
}
}
System.out.println(sum);
}
public static void insertion_sort(float ar[])
{
for(int x=1;x<=ar.length-1;x++)
{
int j=x-1;
float temp1=ar[x];
int temp2=i[x];
int temp3=w[x];
int temp4=v[x];
while(j>=0 && ar[j]<temp1)
{
ar[j+1]=ar[j];
i[j+1]=i[j];
w[j+1]=w[j];
v[j+1]=v[j];
j=j-1;
}
ar[j+1]=temp1;
i[j+1]=temp2;
w[j+1]=temp3;
v[j+1]=temp4;
}
}
}
0 Comments
Please don't enter any spam link in comment box.
Emoji