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.

//PROGRAM FOR GREEDY STRATEGIES FOR THE KNAPSAK PROBLEM
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.0 f;
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.0 f;
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 < n; i++)
for (j = 1; j < n; j++)
if (ratio[j] < ratio[j + 1]) {
temp1 = p[j];
p[j] = p[j + 1];
p[j + 1] = temp1;

temp2 = w[j];
w[j] = w[j + 1];
w[j + 1] = temp2;
}
}
public static void main(String args[]) throws IOException {
System.out.print("Enter the number of objects:-\t");
System.out.print("\nEnter the knapsack capacity:-\t");
float p[] = new float[n + 1];
float w[] = new float[n + 1];
System.out.println("\nEnter the values of profit & weights for each object:-");
for (int i = 1; i <= n; i++) {
System.out.print("Profit of object " + i + " :-\t");
System.out.print("Weight of object " + i + " :-\t");
System.out.println();
}
sortObject(n, p, w);
System.out.println("\nThe optimal solution is:-");
knapsack(m, n, w, p);
}

}
/*                             OUTPUT

Enter the number of objects:-   3
Enter the knapsack capacity:-   20

Enter the values of profit & weights for each object:-
Profit of object 1 :-   15
Weight of object 1 :-   10

Profit of object 2 :-   24
Weight of object 2 :-   15

Profit of object 3 :-   25
Weight of object 3 :-   18

The optimal solution is:-
x:-  1.0
x:-  0.5
x:-  0.0

The profit earned by given optimal solution is:-        31.5
*/

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