Fractional Knapsack Problem

Our last example is that of the fractional knapsack problem. There are many versions of this problem. You can look at one variant of the same problem called the coin change problem, which can be solved via dynamic programming.

For the fractional knapsack problem, we can assume that there is a warehouse with n items, and we maintain two arrays:

1. v as the values of the items
2. w as the weights of the items

So here the ith item has a value of v[i] and a total weight of w[i]. Suppose a thief enters the store with a knapsack, which has a weight capacity X. The goal is to find out how to fill the knapsack so that the total items in the sack have a maximal value. This example problem is shown in the figure below: