Lab Programs

import java.util.*;


public class KnapSack {

    public static void sort(double p[], double w[]) {
        int n = p.length;
        for (int i = 0; i < n - 1; i++) {
            int maxIndex = i;
            for (int j = i + 1; j < n; ++j) {
                if ((p[j]/w[j]) > (p[maxIndex]/w[maxIndex]))
                    maxIndex = j;
            }
            double temp;
            temp = p[i];
            p[i] = p[maxIndex];
            p[maxIndex] = temp;

            temp = w[i];
            w[i] = w[maxIndex];
            w[maxIndex] = temp;
        }
    }

    public static void knapsack(double p[], double w[], int n, int m){
        int i;
        sort(p, w);
        double x[] = new double[n];
        Arrays.fill(x, 0.0);
        double u = m;
        for(i = 0; i<n; i++){
            if( w[i] > u)
                break;
                x[i] = 1.0;
                u = u-w[i];
        }

        if(i<=n)
            x[i] = u/w[i];

        double netProfit = 0.0;
        for(i=0; i<n; i++){
            if(x[i] > 0.0){
                netProfit+=x[i]*p[i];
            }
        }
        System.out.println("Net profit: "+netProfit);
        System.out.println("\nObjects picked in the knapsack are: ");
        System.out.println("\nObject\t Profit\t Weight\t Ratio");
        for (i = 0; i < n; i++) {
            if(x[i] > 0.0){
                System.out.println(i+"\t"+p[i]+"\t"+w[i]+"\t"+x[i]);
            }
        }
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        System.out.println("Enter number of objects: ");
        int n = scan.nextInt();
        double p[] = new double[n];
        double w[] = new double[n];
        
        System.out.println("Enter weight of knapsack: ");
        int m = scan.nextInt();

        System.out.println("Enter profit of each object: ");
        for(int i=0; i<n; i++)
            p[i] = scan.nextDouble();
        
        System.out.println("Enter weight of each object: ");
        for(int i=0; i<n; i++)
            w[i] = scan.nextDouble();

        knapsack(p, w, n, m);
    }
}