Fractional Knapsack Problem (Java and Python Code Solution)

Given a set of N items each having value V with weight W and the total capacity of a knapsack. The task is to find the maximal value of fractions of items that can fit into the knapsack.

Solution -

Java

fractionalknapsack(int[] val,int[] weights, int tot_capacity)                               {

        Items[] iVal = new Items[weight.length];

        for (int i = 0; i < wt.length; i++) {

            iVal[i] = new Item(weight[i], value[i], i);

        }

        Arrays.sort(iVal, new Comparator<ItemValue>() {

            @Override

            public int compare(Items o1, Items o2)

            {

                return o2.cost.compareTo(o1.cost);

            }

        });

        double totalValue = 0d;

        for (Items i : iVal) {

            int curWt = (int)i.weight;

            int curVal = (int)i.value;

            if (capacity - curWt >= 0) {

                capacity = capacity - curWt;

                totalValue += curVal;

            }

            else {

               double fraction = ((double)capacity / (double)curWt);

                totalValue += (curVal * fraction);

               capacity

                    = (int)(capacity - (curWt * fraction));

                break;

            }

        }

        return totalValue;

    }

    static class Items {

        double cost;

        double weight, value, ind;

        public ItemValue(int weight, int value, int ind)

        {

            this.wt = wt;

            this.val = val;

            this.ind = ind;

            cost = new Double((double)value / (double)weight);

        }

    }

Python

def fractionalknapsack(values,weights,Total_capacity):
    n = len(values)

    def score(i) : return values[i]/weights[i]

    items = sorted(range(n)  , key=score , reverse = True)
    sel, value,weight = [],0,0
    for i in items:
        if weight +weights[i] <= capacity:
            sel += [i]
            weight += weights[i]
            value += values [i]
    return value

Problem - InterviewBit