Fractional Knapsack

1. You are given a number n, representing the count of items.

2. You are given n numbers, representing the values of n items.

3. You are given n numbers, representing the weights of n items.

3. You are given a number "cap", which is the capacity of a bag you've.

4. You are required to calculate and print the maximum value that can be created in the bag without overflowing it's capacity.

Note1: Items can be added to the bag even partially. But you are not allowed to put same items again and again to the bag.

Input Format

A number n

v1 v2 .. n number of elements

w1 w2 .. n number of elements

A number cap

Output Format

A decimal number representing the maximum value that can be created in the bag without overflowing it's capacity

1. You are given a number n, representing the count of items.

2. You are given n numbers, representing the values of n items.

3. You are given n numbers, representing the weights of n items.

3. You are given a number "cap", which is the capacity of a bag you've.

4. You are required to calculate and print the maximum value that can be created in the bag without overflowing it's capacity.

Note: Items can be added to the bag even partially. But you are not allowed to put same items again and again to the bag.

Input Format

A number n

v1 v2 .. n number of elements

w1 w2 .. n number of elements

A number cap

Output Format

A decimal number representing the maximum value that can be created in the bag without overflowing it's capacity

Solution:

import java.io.*;

import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int val[] = new int[n],wt[] = new int[n];

        for(int i=0;i<n;i++)

            val[i] = sc.nextInt();

        for(int i=0;i<n;i++)

            wt[i] = sc.nextInt();

        int cap = sc.nextInt();

        

        System.out.println(fractionalKnapsack(n,val,wt,cap));

    }

    

    public static double fractionalKnapsack(int n, int val[], int wt[], int cap){

        Item[] items = new Item[n];

        for(int i=0;i<n;i++){

            items[i] = new Item();

            items[i].val = val[i];

            items[i].wt = wt[i];

            items[i].ratio = val[i] / (double) wt[i];

        }

        

        Arrays.sort(items);

        

        int i = items.length-1;

        double cost = 0;

        

        while(i>=0 && cap > 0){

            if(items[i].wt<=cap){

                cost += items[i].val;

            }else{

                cost += cap * (items[i].ratio);

            }

            cap -= items[i].wt;

            --i;

        }

        

        return cost;

    }

    

    public static class Item implements Comparable<Item>{

        int val;

        int wt;

        double ratio;

        public int compareTo(Item o){

            if(this.ratio == o.ratio)

                return 0;

            else if(this.ratio > o.ratio)

                return +1;

            else return -1;

        }

    }

}