trjhtr

I have tried to implement the Knapsack algorithm in Java. I am trying to do it using the greedy way.

Here is the code:

/*
Knapsack problem: Given w, wieght of items, p , corresponding profits, n the maximum size of
the knapsack, optimize the total profits of the
knapsack. p[i]/w[i] >= p[i+1]/w[i+1], output solution vector x[n]
*/
import java.io.*;
import java.util.*;
class KnapSack


 void sortpbyw(int profits, int weights, int knapSize)
 
 for(int i=0; i < profits.length; i++)
 
 //calculating price per unit weight
 pbyw[i] = (float)profits[i]/weights[i];
 
 //Sorting both the arrays according to the required knapsack property
 for(int i=0; i < profits.length; i++)
 
 float max = pbyw[0];
 int pos = 0;
 for(int j = 0; j < weights.length; j++)
 
 if(max < pbyw[j])
 
 max = pbyw[j];
 pos = j;
 
 
 profits[i] = profits[pos];
 weights[i] = weights[pos];
 pbyw[pos] = -1;
 
 for(int i=0; i< profits.length; i++)
 
 System.out.println(profits[i]+"t"+weights[i]);
 
 //store the solution
 double x = new double[pbyw.length];
 for(int i=0; i<pbyw.length; i++)
 
 x[i] = 0.0;
 

 double U = knapSize;
 int j;
 int n = profits.length;

 for(j=0; j<n; j++)
 
 if(weights[j]>U)
 
 break;
 
 x[j] = 1.0;
 U = U-weights[j];
 

 if(j<=n)
 
 x[j] = U/weights[j];
 
 //displaying the answers
 double value = 0;
 System.out.println("The solution vector is:");

 for(int i=0; i<n; i++)
 
 System.out.print(x[i]+"t");
 value = value+(x[i]*profits[i]);
 
 System.out.println();
 System.out.println("The knapsack value is: "+value);
 

 public static void main(String args) throws IOException
 
 BufferedReader br = new BufferedReader(new
 InputStreamReader(System.in));
 System.out.println("Enter the size of the array:");
 String line = br.readLine();
 int size = Integer.parseInt(line);
 int weights = new int[size];
 int profits = new int[size];
 System.out.println("Enter the maximum size of the knapsack:");
 String line2 = br.readLine();
 System.out.println("Enter the elements in the weights one by one:");

 for ( int i = 0; i < size; i++ )
 
 String line3 = br.readLine();
 weights[i] = Integer.parseInt(line3);
 

 System.out.println("Enter the elements in the profits corresponding to weights one by one:");

 for ( int i = 0; i < size; i++ )
 
 String line4 = br.readLine();
 profits[i] = Integer.parseInt(line4);
 
 int knapSize = Integer.parseInt(line2);//Sort profits/weights such that profits[i]/weights[i] >=profits[i+1]/weights[i+1]
 KnapSack ks = new KnapSack();
 ks.sortpbyw(profits,weights,knapSize);
 

I have the following questions about my code:

1. Is there a better way to sort 2 profits and weights array according to the knapsack property?




2. Is there a better way to implement this algorithm using the greedy approach?




3. How can I further optimize my code?