Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!cs.utexas.edu!uwm.edu!dogie.macc.wisc.edu!wuarchive!cec2!news
From: dg0951@cec1.wustl.edu (Daniel Geist)
Newsgroups: comp.theory
Subject: Knapsack problem
Message-ID: <1990Mar21.195010.4623@cec1.wustl.edu>
Date: 21 Mar 90 19:50:10 GMT
Sender: news@cec2 (USENET News System)
Distribution: usa
Organization: Washington University, St. Louis MO
Lines: 12

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