Fractional Knapack as asked in an interview

Question

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<Pair> 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<Pair> comparator = new FractionComparator();
        PriorityQueue<Pair> queue   = new PriorityQueue<Pair>(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<Pair>
{
    @Override
    public int compare(Pair p1, Pair p2)
    {
        if ((p2.value / p2.weight) < (p1.value / p1.weight)) return -1;
        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.

Answer 1

        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.

Answer 2

Few things may.

First of all, I am not sure you are solving the right problem. Your solution adds fractions of objects, whereas classic knapsack assumes that the objects are indivisible. Sorry I didn't pay attention to the title.

Second, when you add something to the knapsack, either a == capacity and the knapsack becomes full, or a == max.weight and the object is added in its entirety. In both cases it makes no sense to deal with the remaining part of the object.

Since there is no need to deal with the remaining parts, you don't need a priority queue. Just sort your objects in the decreasing order of "value density".

Finally, the comparator may just

    return p2.value / p2.weight - p1.value / p1.weight;

Answer 3

Why is it called Pair? The problem speaks of items, so a name like Item for the class appears to be more appropriate.

If you look at the FractionComparator alone it appears to be strange: what's the purpose of this? Sure, it compares fractions, but we can already compare double, so what's the point of this class? "Fraction" is a very generic term. I'd much prefer a more meaningful name that explains some of the context this class is used in.@vnpused the term "value density" in his answer, which describes a lot better what's actually compared. I suggest a name like ValueDensityComparator