posted 8 years ago
Well, the knapsack interpretation is more exciting than Paul's "buy nothing" interpretation, which yields an extremely trivial problem. (Which of course is his point.) I believe the difference is in how we interpret "keep the difference [between two values] to a minimum". Steve is implicitly assuming that what is meant here is to keep the *absolute value* of the difference to a minimum. While Paul is happy to let the magnitude of the number get as large as possible, as long as it's negative. Paul's interpretation may be literally correct, but I think it's pretty ambiguous. What does "difference between A and B" mean? Is it A-B? Or B-A? Depending on the answer, the solution might be to pick *all* of the players, rather than none. At least if we take the absolute value, that ambiguity doesn't matter, and it does yield a more interesting problem - albeit one that's already discussed extensively in the literature.