[comp.theory] Knapsack problem

dg0951@cec1.wustl.edu (Daniel Geist) (03/22/90)

The knapsack problem is a very well known 0-1 programming
problem: 
	 
         __n                      __n
Maximize \                        \
	 /_ Ci*Xi   provided that /_Vi*Xi <= Vo
	 i=1                      i=1

The problem itself is NP for Ci,Vi real. However I wonder
if given the optimal solution there is a way to determine
the "second best" solution in polynomial time?
			    Danny Geist