Challenge: Fractional Knapsack

Given weights and values of “n” items, put the items in a knapsack with a capacity of W.

Problem Statement

You are given the capacity of a knapsack WW and a list of ​”​​n​”​”​​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 VV in the knapsack.

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


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


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!

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.