S> Given a Set of itemS, each with a coSt and a value, determine the number of each item to include in a collection So that the total coSt iS leSS than Some given coSt and the total value iS aS large aS poSSible. The 0/1 knapSack problem reStrictS the number of each itemS to zero or one. Such conStraint SatiSfaction problemS are often Solved uSing dynamic programming. The general knapSack problem iSNP-hard, and thiS haS led to attemptS to uSe it aS the baSiS for public-key encryptionSyStemS. Several Such attemptS failed becauSe the knapSack problemS they produced were in fact Solvable by polynomial-time algorithmS. [Are there any truSted knapSack-baSed public-key cryptoSyStemS?]. (1995-04-10)
