# 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<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
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);
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.

        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
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.

• I see that changing code logic does reduce the duplicate computation. I think I need to re-think my first solution and make this as a habit because generally the solution that comes into mind is more mathematical. Thanks. – CodeYogi Sep 21 '16 at 2:10
• Having said that I would like to know if there is any way to improve the Pair and FractionComparator? and something about visibility would help too like when to have inner classes and etc. – CodeYogi Sep 21 '16 at 2:12

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;

• With that comparator, I would be worried that small differences would get converted to 0 instead of -1/1 since it gets truncated to an integer. – FDinoff Sep 20 '16 at 23:40
• Can I shift comparison logic to Pair? if yes would it be more OO oriented? – CodeYogi Sep 21 '16 at 2:16
• One more thing, currently I am assuming that client code would give me a priority queue but is this a nice approach or should I ask client to give me just a list of pairs and do optimization in my code? – CodeYogi Sep 21 '16 at 2:18

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

• Hmm, generally this is most confusing part for me. FractionComparator as name suggests compares fraction and I could use it anywhere else too on the other hand ValueDensityComparator is more domain specific and might help the reader to understand the intent better although its still not a good name. – CodeYogi Sep 21 '16 at 2:14
• @CodeYogi Incorrect, the FractionComparator is not more general. Its naming is more general, but its contract is to compare Pairs, which are not general: they have a value and a weight, so their fraction will always be a density. Therefore either the naming is wrong (as the answer proposes) or the contract is wrong - but you'll have a hard time fixing that... To find a middle ground, maybe simply let Item extend Comparable<Item>is an easy fix. – MrBrushy Oct 27 '16 at 15:04