g₀(m) = g₀(6) = the value of an optimal solution to KNAP(1,3,6) (from KNAP(1,n,m) )

1. def.      g₀(m) = max{g₁(m), g₁(m-w₁) + p₁}

2. def.      g₀(6) = max{g₁(6), g₁(^6-2₄) + 1}

3. def.      g1(6) = max{g2(6), g2(6-w23) + 2}

4. def.      g2(6) = max{g3(6), g3(6-w32) + 5}
        but n = 3 and hence g3 = gn. Given: gn(y)=0 for all y > 0

5. so        g₂(6) = max{0, 0+5} = 5

6. using 3,5      g₁(6) = max{5, g₂(3) + 2}

7. def.      g2(3) = g3(3), g3(3-w33-4) + 5}
        but n = 3 and hence g3 = gn. Given: gn(y)= - for all y < 0 ( y < 0 indicates weight of negative value - can't do)

8. so       g₂(3) = max{0,- } = 0

9. 6 becomes      g₁(6) = max{5, 2} = 5

10. 2 becomes      g₀(6) = max{5, g₁(4) + 1}

11. def.      g1(4) = max{g2(4), g2(4 -w21) + 2}

12. def.      g2(4) = max{g3(4), g3(4 -w30) + 5} = max{0,5} = 5

13. def.      g2(1) = max{g3(1), g3(1 -w3-3) + 5} = max{0,-} = 0

14. 11 becomes      g₁(4) = max{5, 2} = 5

15. 2 (with 9 and 14)      g₀(6) = max{5, 5 + 1} = 6