[ 0/1 Knapsack] Book example 5.6

The 0/1 knapsack problem is similar to the knapsack problem of Section 4.2 except that the xi's are restricted to have a value of either 0 or 1. Using KNAP(l,j,y) to represent the problem
Note this is an ("el", j, y) not a one... it denotes the first element in the sequence(l), the last (j), and the knapsack capacity(y)) the knapsack problem is KNAP(l,n,m).

Let y1, y2, . . ., yn be an optimal sequence of 0/1 values for x1, x2, . . ., xn, respectively.

If y1 = 0, then y2, y3, . . ., yn must constitute an optimal sequence for KNAP(2,n,m). If it does not, then y1, y2, . . ., yn is not an optimal sequence for KNAP(l,n,m).
(The two solutions would be the same so if one is not optimal the other was not to begin with)

If y1 = 1, then y2, y3, . . ., yn must constitute an optimal sequence for KNAP(2,n,m - w1). If it isn't, then there is another 0/1 sequence z2, z3, . . ., zn such that 2 <i <n   wizi    <   m - wi and    2 <i <n    pizi    >    2 <i <n    piyi.  
(If this new solution is better we still have found a subproblem choice that is optimal given our first choice...we continue)
Hence, the sequence y1,z2, z3, . . ., zn is a sequence for the problem with greater value.

Again, the principal of optimality applies (the subsolutions KNAP(2,n,m) and KNAP(2,n,m - w1) were solutions to the subproblems).