Challenge: Fractional Knapsack

Problem Statement

You are given the capacity of a knapsack $W$ and a list of $​”​​n​”$​​ items that each have a certain value. Fractions of each item can be placed in the knapsack. Your goal is to implement a function for getting the maximum possible total value of $V$ in the knapsack.

Note: This problem is also known as the $continuous\ knapsack$ problem.

Input

the inputs are the items as $(value, weight)$ pairs and the knapsack capacity $W$.

Output

The output is the maximum possible value.

Sample input

double[] weights = {2, 1, 6, 0.5, 0.25, 7}; 
double[] values = {50, 70, 100, 50, 30, 99}; 
int capacity = 10; 

Sample output

double result =  303.54;

💡 Did you know?
In the 0/1 Knapsack problem, we are not allowed to break the items. We either take the whole item or do not take it at all. However, here we can split the items.

Coding exercise

Take a close look and design a step-by-step algorithm before jumping to the implementation. This problem is designed for your practice, so try to solve it on your own first. If you get stuck, you can always refer to the hint and solution provided in the code tab. Good Luck!