Fractional Knapsack in Java

Question

So I solved Fractional Knapsack problem:

There are n items in a store. For i =1,2, . . . , n, item i has weight wi > 0 and worth vi > 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 xi of object i, where 0 ≤ xi ≤ 1. Item i contributes xiwi to the total weight in the knapsack, and xivi to the value of the load. In Symbol, the fraction knapsack problem can be stated as follows. maximize nSi=1 xivi subject to constraint nSi=1 xiwi ≤ 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 nSi=1 xiwi = W

import java.util.Scanner;


public class FractionalKnapsack{

 static int[] value;
 static int[] weight;
 static float[] ratio;
 static int knapSackWeight;


 static void getMaximumBenefit() {

     int currentWeight = 0;
     float benefit = 0;

     while(currentWeight < knapSackWeight) {

        int item = getMaxRatioItem();

        //No items left
        if(item == -1) {

            break;
       }

       for(int i=0;i<weight[item];i++) {

           if(currentWeight+ratio[item]<=knapSackWeight) {
               currentWeight++;
               benefit = benefit + ratio[item];
            }
       }


        //Removing the item from array
        ratio[item] = 0;
     }

    System.out.println("Weight: " + currentWeight + " Benefit: " + benefit);

 }

static int getMaxRatioItem() {

    float maxRatio = 0;
    int ratioIndex = -1;

    //Getting max ratio
    for(int i=0;i < ratio.length;i++) {

        System.out.println(ratio[i]);

        if(ratio[i] > maxRatio) {

            maxRatio = ratio[i];
            ratioIndex = i;
        }
    }

    return ratioIndex;
}


  public static void main(String[] args) {

    Scanner in = new Scanner(System.in);

    int n = in.nextInt();
    value = new int[n];
    weight = new int[n];
    ratio = new float[n];

    for (int i = 0; i < n; i++) {
        weight[i] = in.nextInt();
        value[i] = in.nextInt();
        ratio[i] = (float)value[i] / weight[i];
    }

   knapSackWeight = in.nextInt();

    getMaximumBenefit();

}
}

Is there any better solution? The running time will be n^2?

Answer 1

I am not going to review the actual algorithm. However, there are some improvements possible:

1

static int[] value;
static int[] weight;
static float[] ratio;
static int knapSackWeight;

You expose the state of your algorithm to entire package. Also, your implementation is not thread-safe: if two threads call the getMaximumBenefit more or less simultaneously, they might interfere. One way to circumvent this issue is to make sure that getMaximumBenefit constructs an object holding the state of computation and manipulate only that object throughout the computation.

2

getMaximumBenefit should be declared public. Otherwise no-one will be able to call it outside of your (default) package.

3

Since getMaxRatioItem is a helper routine, it would be nice to declare it private.

4

int ratioIndex = -1;

What is the purpose of the value -1? It would be nice to declare a constant:

private static final int NO_ITEMS_LEFT = -1;

and then write

int ratioIndex = NO_ITEMS_LEFT;
...
if (item == NO_ITEMS_LEFT) {
    return benefit;
}

A nice point here is that if you need for some reason to change the value of that constant, you will have to edit its definition only in one place. The rule here is not to hardcode magic values, but make named constants out of them.

5

System.out.println(ratio[i]);

Printing within an algorithm is a bad taste (unless debugging). Think about how much output you get in production whenever computing a large problem instance.

6

getMaximumBenefit should return some simple data structure representing the result, not just print it on standard output.

Summa summarum

All in all, I had this in mind:

import java.util.Objects;
import java.util.Scanner;

public class FractionalKnapsackSolver {

    private static final int MINIMUM_CAPACITY = 1;
    private static final int NO_ITEMS_LEFT = -1;

    private final int[] values;
    private final int[] weights;
    private final float[] ratios;
    private final int knapsackCapacity;

    private FractionalKnapsackSolver(final int[] values,
                                     final int[] weights,
                                     final float[] ratios,
                                     final int knapsackCapacity) {
        this.knapsackCapacity = checkCapacity(knapsackCapacity);
        this.values = Objects.requireNonNull(values, 
                                             "The value array is null.");
        this.weights = Objects.requireNonNull(weights,
                                              "The weight array is null.");
        this.ratios = Objects.requireNonNull(ratios, 
                                             "The ratio array is null.");
        checkWeightArrayLength();
        checkRatioArrayLength();
    }

    private int checkCapacity(final int capacity) {
        if (capacity < MINIMUM_CAPACITY) {
            throw new IllegalArgumentException(
                    "Nonpositive capacity given: " + capacity + "." +
                    "Must be at least " + MINIMUM_CAPACITY + ".");
        }

        return capacity;
    }

    private void checkWeightArrayLength() {
        if (weights.length != values.length) {
            throw new IllegalArgumentException(
                    "The length of the weight array (" + weights.length + 
                    ") does not match the length of the value array (" +
                    values.length + ").");
        }
    }

    private void checkRatioArrayLength() {
        if (ratios.length != values.length) {
            throw new IllegalArgumentException(
                    "The length of the ratio array (" + ratios.length + 
                    ") does not match the length of the value array (" +
                    values.length + ").");
        }
    }

    public static float computeBenefit(final int[] values,
                                       final int[] weights,
                                       final float[] ratios,
                                       final int knapsackCapacity) {
        final FractionalKnapsackSolver solver = 
                new FractionalKnapsackSolver(values, 
                                             weights, 
                                             ratios, 
                                             knapsackCapacity);

        return solver.compute();
    }

    private int getMaximumRatioItem() {
        float maximumRatio = 0.0f;
        int maximumRatioIndex = NO_ITEMS_LEFT;

        for (int i = 0; i < ratios.length; ++i) {
            if (maximumRatio < ratios[i]) {
                maximumRatio = ratios[i];
                maximumRatioIndex = i;
            }
        }

        return maximumRatioIndex;
    }

    private float compute() {
        int currentWeight = 0;
        float benefit = 0.0f;

        while (currentWeight < knapsackCapacity) {
            final int item = getMaximumRatioItem();

            if (item == NO_ITEMS_LEFT) {
                return benefit;
            }

            for (int i = 0; i < weights[item]; ++i) {
                if (currentWeight + ratios[item] <= knapsackCapacity) {
                    currentWeight++;
                    benefit += ratios[item];
                }
            }

            ratios[item] = 0;
        }

        return benefit;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        final int n = in.nextInt();
        final int[] values = new int[n];
        final int[] weights = new int[n];
        final float[] ratios = new float[n];

        for (int i = 0; i < n; ++i) {
            weights[i] = in.nextInt();
            values[i] = in.nextInt();
            ratios[i] = (float)(values[i]) / weights[i];
        }

        final int knapsackCapacity = in.nextInt();

        System.out.println(computeBenefit(values, 
                                          weights, 
                                          ratios,
                                          knapsackCapacity));
    }
}

Hope that helps.

Answer 2

Optional solution has complexity O(n*log n).

First, you need sort your items by ratio. If you take merge sort, for example, it will take O(n*log n). And finally, you iterate items in order of decreasing ratio. On each iteration you will take item with maximum ratio. It will take O(n).

So, total complexity is O(n*log n + n) = O(n*log n)