Implementing Greedy Knapsack Algorithm in Java

According to Wikipedia,

The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a mass and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

import java.io.*;
class GreedyKnapsack
{
public static void knapsack(float m,int n,float w[],float p[])
{
int i;
float x[]=new float[n+1];
float profit=0.0f;
for(i=1;i<=n;i++) x[i]=0; float U=m; for(i=1;i<=n;i++) { if(w[i]>U) break;
x[i]=1.0f;
U-=w[i];
}
if(i<=n) x[i]=U/w[i]; for(i=1;i<=n;i++) { System.out.println("x["+i+"]:-\t"+x[i]); profit=profit+(p[i]*x[i]); } System.out.println("\nThe profit earned by given optimal solution is:-\t"+profit); } public static void sortObject(int n, float p[],float w[]) { int i,j; float temp1,temp2; float ratio[]=new float[n+1]; for(i=1;i<=n;i++) { ratio[i]=p[i]/w[i]; } for(i=1;i

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.