• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Optimization problem

 
Harshvardhan gupta
Greenhorn
Posts: 8
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.

How do i go about this problem please help.
 
fred rosenberger
lowercase baba
Bartender
Posts: 12084
29
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 20725
30
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
My advisers have put their advice in a very obscure fashion.

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: 602
7
Mac OS X Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 3028
10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic