CSCI 356: Design and Analysis of Algorithms

[ 0/1 Knapsack] Book example 5.10

Let y₁, y₂, . . ., y_n be an optimal solution to KNAP(1,n,m). Then for each j, 1 < j < n,
y₁, . . ., y_j and y_j+1, . . ., y_n must be optimal solutions to the problems
KNAP(1, j,

1 <i <j w_iy_i) and KNAP(j+1, n, m -

1 <i <j w_iy_i) respectively.
This observation allows us to generalize to

_i+1

Where g_n(y) = 0 for all y > 0 for all the n's higher than the n we are going to, the values are 0, i.e., we do not choose them
and g_n(y) = - for all y < 0 if there is no more capacity left in the sack, we make the solution so small it cannot be the chosen one