主观题：Another way to approximate 0-1 knapsack problem

let's take another look at the fractional knapsack problem.  It can be shown that there is an optimal packing with at most one split item. Based on this observation, the 2-approximation algorithm for the 0-1 knapsack problem follows easily. Obviously, in the fractional case, if the split item has a relatively small value, it would result a good approximation for the integral case by simply discarding the split one (the items remain in the knapsack are all integral). 

Along this line, try to design a better approximation algorithm by bounding value of the split item (to be discarded later).






答案：