# Optimization problem

Harshvardhan gupta
Greenhorn
Posts: 8
There are N players eligible to play in the coming season. Each player has a fixed cost ranging from 0 to C based on his previous performance. You are first one allowed to pick a team. You can pick as many players as you like, but you have limited resources. Your advisers tell you that, if you keep the difference between the sum of the costs of players you buy and the ones you donâ€™t to minimum, you stand to make the best use of your resources.

fred rosenberger
lowercase baba
Bartender
Posts: 12196
35
You can always brute force it.

for each player, you can either pick them, or not pick them. So, there are 2^n ways to pick a team. For each option, find the cost for those you do pick, the cost for those you don't, and find the smallest difference.

Paul Clapham
Sheriff
Posts: 21416
33

Let T be the total cost of all players, and let P be the cost of players that I pick. Then the cost of players that I don't pick is T - P. And the difference between the cost of players that I pick and the cost of players that I don't pick is P - (T - P), or 2P - T.

Now T is a constant. So min(2P - T) = 2 min(P) - T.

In other words I simply need to minimize the cost of players that I pick. Which is trivially simple -- I just don't pick any players. In which case the metric proposed by my advisers is -T, which is indeed the smallest difference.

So my advisers have just provided useless information. But perhaps there's something more to the problem which hasn't been stated; otherwise it's pretty unexciting.

Steve Fahlbusch
Bartender
Posts: 605
7
I take it there must be more that was not passed on, otherwise this is just a knapsack problem with the size being 1/2 the cost of all players?

You're right - not very exciting.

Mike Simmons
Ranch Hand
Posts: 3090
14
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.