is an instance of the Binary Knapsack Problem (BKP) form max a n

j = 1cjxj s.t. a n

j = 1ajxj … b x1,c, xn = 0 or 1

(d) The Dynamic Programming algorithm of 14-1 solves instances of (BKP) by computing a longest path in a network across n stages with at most b states each. Explain why those computations are polynomial in the magnitudes of the constants, but exponential in the standard binary encoding.

(e) Explain why

(d) makes (BKP) pseudopolynomially solvable.

(f) Comment on what

(d) and

(e) tell us about how easy or hard (BKP) instances are to solve, at least those of modest size.

(g) (BKP) is known to be NP-Hard, so all problems in NP reduce to it. Would you expect manageable instances like those of

(f) to be the kinds that result from reduction of a very hard problem form in NP?

Explain.