Harshvardhan gupta

Greenhorn

Posts: 8

posted 6 years ago

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.

How do i go about this problem please help.

posted 6 years ago

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.

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

posted 6 years ago

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.

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.

Mike Simmons

Ranch Hand

Posts: 3090

14

posted 6 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.Consider Paul's rocket mass heater. |