Categories
interview

Knapsack Bounded(1/0), Unbounded, Bounded/Fraction, Unbounded/Fraction Solutions

Bounded Knapsack (1/0) Solution in Java using Dynamic Programming
There are few items with weights and values, we need to find the items that contribute the maximum value that can be stored in knapsack of a particular capacity.
There are only 2 choices for each item, i.e. it can either be included or excluded from the bag.
Space complexity O(i*(capacity+1))
Time complexity
O(i*(capacity+1))

Output

Using Recursion

This is very inefficient.

Output

Time Complexity = O(2^n).

Bounded Knapsack with Fractions allowed
In the above problem if we are allowed to include fractions, then we sort the items based on their value to weight ratios in descending order and include them in the knapsack, until it is full.

Output

Unbounded Knapsack solution
In this approach we use Dynamic programming to store the capacities incrementally to get the required maximum value at capacity.
Time complexity = O(i*(c+1))
Space complexity = O(c+1)

Output

Unbounded Knapsack with Fractions allowed
This is a straightforward implementation, as we need to find the maximum ratio among the given items (value/weight) and then multiply it with the capacity of the bag.
Time complexity = O(i)
Space complexity = O(1)

Output