aspose file tools*
The moose likes Programming Diversions and the fly likes Optimization problem Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Spring in Action this week in the Spring forum!
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "Optimization problem" Watch "Optimization problem" New topic
Author

Optimization problem

Harshvardhan gupta
Greenhorn

Joined: Apr 04, 2010
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.

How do i go about this problem please help.
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11406
    
  16

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.


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18651
    
    8

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

Joined: Sep 18, 2000
Posts: 570
    
    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

Joined: Mar 05, 2008
Posts: 3018
    
  10
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.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Optimization problem