Fractional Knapack as asked in an interview

Description:


Given the Knapsack capacity and the weight and value of some items,
find a way to maximize the value in the given Knapsack.

Code:

/* Name of the class has to be "Main" only if the class is public. */
class Main
{
    public static float KnapSack(float capacity, PriorityQueue queue) {
        float val = 0;
        while (queue.size() > 0) {
            if (capacity == 0) return val;
            Pair max = queue.poll();
            float a = Math.min(max.weight, capacity);
            val += a * (max.value / max.weight);
            if (max.weight - a > 0) // to prevent division by zero
                queue.add(new Pair(max.value, max.weight - a));
            capacity -= a;
        }
        return val;
    }

    public static void main (String[] args) throws java.lang.Exception
    {
        Comparator comparator = new FractionComparator();
        PriorityQueue queue   = new PriorityQueue(3, comparator);
        queue.add(new Pair(20, 4));
        queue.add(new Pair(18, 3));
        queue.add(new Pair(14, 2));
        System.out.println(KnapSack(7, queue));
    }
}

// Degenerate value class
class Pair {
    final float value;
    final float weight;

    Pair(float value, float weight) {
        this.value  = value;
        this.weight = weight;
    }
}

class FractionComparator implements Comparator
{
    @Override
    public int compare(Pair p1, Pair p2)
    {
        if ((p2.value / p2.weight)  (p1.value / p1.weight)) return  1;
        return 0;
    }
}

Question:

From interview perspective what may raise eyebrows of an interviewer?

Having said that personally I am interested in readability and reducing code redundancy, the one thing where I am feeling uncomfortable is Pair class although I made it for readability but for changing even a field name I have to d changes in many places.

Last but not the least I think some knowledge about scope and visibility would be good.

float val = 0;
        while (queue.size() > 0) {
            if (capacity == 0) return val;
            Pair max = queue.poll();
            float a = Math.min(max.weight, W);
            val += a * (max.value / max.weight);
            if (max.weight - a > 0) // to prevent division by zero
                queue.add(new Pair(max.value, max.weight - a));
            capacity -= a;
        }
        return val;

Consider

float val = 0;

        while (!queue.isEmpty()) {
            Pair max = queue.poll();
            if (max.weight < capacity) {
                val += max.value;
                capacity -= max.weight;
            } else {
                return val + capacity * (max.value / max.weight);
            }
        }

        return val;

The canonical way to check if a collection is empty is to call the isEmpty() method.

We check that the capacity hasn't been reduced to zero before the end of the loop rather than at the beginning. Note that a side effect of this is that we don't care about passing 0.0. In the original code, floating point rounding could allow you to pass the equality check.

Rather than take Math.min, we compare max.weight and capacity. This simplifies the logic, as we don't have to multiply and divide by the same value in the expected case. We only do that for the final item.

StackExchange Code Review Q#141948, answer score: 3