This week's giveaway is in the Spring forum.
We're giving away four copies of REST with Spring (video course) and have Eugen Paraschiv on-line!
See this thread for details.
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 REST with Spring (video course) this week in the Spring forum!
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "Optimization problem" Watch "Optimization problem" New topic

Optimization problem

Harshvardhan gupta

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

Joined: Oct 02, 2003
Posts: 11923

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

Joined: Oct 14, 2005
Posts: 19874

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

Joined: Sep 18, 2000
Posts: 596

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: 3028
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:
subject: Optimization problem
It's not a secret anymore!