Source code online books for professionals by professionals

The knapsack problem and integer programming. The knapsack problem involves choosing a valuable subset of a set 
of items, under certain constraints. In the (bounded) fractional case, you have a certain amount of some substances, each 
of which has a unit value (value per unit of weight). You also have a knapsack that can carry a certain maximum weight. 
The (greedy) solution is to take as much as you can of each substance, starting with the one with the highest unit value. 
For the integral knapsack problem, you can take only entire items—fractions aren’t allowed. Each item has a weight and 
a value. For the bounded case (also known as 0-1 knapsack), you have a limited number of objects of each type. (Another 
perspective would be that you have a fixed set of objects that you either take or not.) In the unbounded case, you can take 
as many as you want from each of a set of object types (still respecting your carrying capacity, of course). A special case 
known as the subset sum problem involves selecting a subset of a set of numbers so that the subset has a given sum. These 
problems are all NP-hard (see Chapter 11), but admit pseudopolynomial solutions based on dynamic programming  
(see Chapter 8). The fractional knapsack case, as explained, can even be solved in polynomial time using a greedy strategy 
(see Chapter 7). Integer programming is, in some ways, a generalization of the knapsack problem (and is therefore 
obviously NP-hard). It is simply linear programming where the variables are constrained to be integers.