1. Why not solve the knapsack problem in the same way as the matrix-chain and optimum binary search tree problems: by minimizing, for k from I to M, the sum of the best value achievable for a knapsack of size k and the best value achievable for a knapsack of size M-k?
2. Extend the program for the shortest-paths problem to include a procedure paths that fills an array path with the shortest path from i to j. This procedure should take time proportional to the length of the path each time it is called, using an auxiliary data structure built up by a modified version of the program given in Chapter 32.