In our second example, you are given a fixed budget and your goal is to purchase
a number of computers so that to maximize the total performance.
Again, we assume that the part of your input in this case is a set of available
computers or machine and for each machine you know its price and its performance.
Both the considerated problems can be easily seen to be
special cases of the following general problem known as the Knapsack Problem.
In this problem,
you are given a set of items together with the total capacity of the knapsack.
For each item you know its value and its weight.
For example, the value of the green item here is four, while its weight is 12.
And your goal is to select the subset of items such that the total value is as
large as possible while the total weight is at most, the capacity of the knapsack.
In our case, the total capacity of the knapsack is equal to 15.
There are two versions of the knapsack problem.
Fractional knapsack and discrete knapsack.So, for
the fractional version, which you are already familiar with, you can take any
fraction off of any item, while in the discrete version, for each item,
you either take the whole item in your knapsack or you do not take it at all.
So, in turn, the discrete version has two variants also.
So, the first variant is knapsack with repetitions.
So in this case, you are given an unlimited quantity of each item.
While in the knapsack without repetitions,
you are given just a single copy of each item.
So we know already that the fractional knapsack problem can be solved
by a simple greedy algorithm.
Such an algorithm at each iteration just picks an element,
an item with the currently maximal value per unit of weight.
This strategy, however, doesn't work for
the discrete version of the knapsack problem.
So instead of using greedy strategy,
we will design a dynamic programming solution to find an optimal value.
