How to implement an algorithm for the Fractional Knapsack Problem

In this Java tutorial, we are going to implement an algorithm for the fractional knapsack problem.

Knapsack Problem Description

A thief finds a very big loot than his bag size. We have to help him to find the most valuable combination of items assuming that any fraction of a loot item can be put into his bag.

Input Format:- The first line of the input contains the number () of items and the capacity (W) of a knapsack.
The next lines define the values and weights of the items. The i-th line contains integers Vi and Wi the value and the weight of the i-th item.

Output Format:- Output the maximum value of fractions of items that fit into his bag.

Step By Step Approach – Knapsack problem in Java

1. First, we have to find the value of the item per kg. To find this we have to calculate the value of “Vi/Wi“.
2. Now compare the value of each item per kg.
3. The item whose value is highest goes first in the bag and compare with the maximum weight bag can take. if the bag is full then it stops here.
4. If not then, second highest goes in the bag and compare with the maximum weight bag can take.
5. The same process goes on and on until the bag is full.

import java.util.Scanner;

public class CodeSpeedy {

    private static int getMaxIndex(int[] weight, int[] values) {
        int max_i = 0;
        double max = 0;

        for (int i = 0; i < weight.length; i++) {
            if (weight[i] != 0 && (double) values[i] / weight[i] > max) {
                max = (double) values[i] / weight[i];
                max_i = i;
            }
        }
        return max_i;
    }

    private static double getOptimalValue(int capacity_is, int[] values, int[] weight) {
        double value = 0.0;

        for (int i = 0; i < weight.length; i++) {
            if (capacity_is == 0)
                return value;
            int index = getMaxIndex(weight, values);
            int a = Math.min(capacity_is, weight[index]);
            value += a * (double) values[index] / weight[index];
            weight[index] -= a;
            capacity_is -= a;
        }
        return value;
    }

    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);
        int p = scanner.nextInt();
        int capacity_is = scanner.nextInt();
        int[] values = new int[p];
        int[] weight = new int[p];
        for (int i = 0; i < p; i++) {
            values[i] = scanner.nextInt();
            weight[i] = scanner.nextInt();
        }
        System.out.println(getOptimalValue(capacity_is, values, weight));
    }
}

INPUT  

3 50
60 20
100 50
120 30

OUTPUT

180.0000