Fractional Knapsack Problem Solution [Fractional Knapsack][Java]

This program solves the fractional knapsack problem.

The problem :

There are n items in a store. For i =1,2, . . . , n, item i has weight w_i > 0 and worth v_i > 0. Thief can carry a maximum weight of W pounds in a knapsack. In this version of a problem the items can be broken into smaller piece, so the thief may decide to carry only a fraction x_i of object i, where 0 ≤ x_i ≤ 1. Item i contributes x_iw_i to the total weight in the knapsack, and x_iv_i to the value of the load.
In Symbol, the fraction knapsack problem can be stated as follows.
maximize ⁿS_i=1 x_iv_i subject to constraint ⁿS_i=1 x_iw_i ≤ W
It is clear that an optimal solution must fill the knapsack exactly, for otherwise we could add a fraction of one of the remaining objects and increase the value of the load. Thus in an optimal solution ⁿS_i=1 x_iw_i = W.

The fractional knapsack problem solution is based on the greedy approach where the best-looking step is taken at each choice. (In this case, the highest ratio item is selected from all the items).

Code:

import java.util.Scanner;

public class FractionalKnapsack {

    double weight[];
    double benefit[];
    double ratio[];
    double W;

    FractionalKnapsack() {
        Scanner scan = new Scanner(System.in);
        System.out.println("Enter the number of items in the store: ");
        int nItems = scan.nextInt();
        System.out.println("Enter the (weight and benefit) of items: ");
        weight = new double[nItems];
        benefit = new double[nItems];
        ratio = new double[nItems];

        for (int i = 0; i < nItems; ++i) {
            weight[i] = scan.nextDouble();
            benefit[i] = scan.nextDouble();
            ratio[i] = benefit[i] / weight[i]; 
        }

        System.out.println("Enter the weight of the knapsack: ");
        W = scan.nextDouble();
    }

    int getNext() {
        double highest = 0;
        int index = -1;
        for (int i = 0; i < benefit.length; ++i) {
            if (ratio[i] > highest) {
                highest = ratio[i];
                index = i;
            }
        } 
        return index;
    }

    void fill() {
        double cW = 0; //current weight
        double cB = 0; //current benefit 

        System.out.print("\nItems considered: ");
        while (cW < W) {
            int item = getNext();        //next highest ratio
            if (item == -1) {
                //No items left
                break;
            }

            System.out.print((item+1)+" ");
            if (cW + weight[item] <= W) {
                cW += weight[item];
                cB += benefit[item];
                //mark as used for the getNext() (ratio) function
                ratio[item] = 0;
            } else {
                cB += (ratio[item] * (W - cW));
                cW += (W - cW);
                break;  //the knapsack is full
            }
        }
        System.out.println("\nMax Benefit = " + cB + ", Max Weight = " + cW);
    }

    public static void main(String[] args) {
        FractionalKnapsack fk = new FractionalKnapsack();
        fk.fill();
    }
}

Output:

Enter the number of items in the store:
5
Enter the (weight and benefit) of items:
20 4
40 3
10 1
35 5
40 2
Enter the weight of the knapsack:
50

Items considered: 1 4
Max Benefit = 8.285714285714285, Max Weight = 50.0