CODEWITHSUNDEEP
javac++algorithmdata-structures
bunnybare
bunnybare

Reputation: 181

Maximize multiple buckets sum?

Have 180 balls.

Have 70 buckets.

Each ball's value depend on which bucket it's in:

ball1 = { 1, 14, 2, 3, 4 ... } //70 values in total for each bucket
ball2 = { 24, 2, 23, 2, 5 ... }
...

Each bucket has a max number balls it can carry, but total number of balls the 70 buckets can carry is 180, i.e. all 180 balls will fit exactly. (every bucket has to carry at least 1 ball)

{bucket1, 3} {bucket2, 1} { bucket3, 2} {bucket4, 1} ...

How do you maximize the ball placement on this?

I tried to bruteforce, and quickly regretted it after counting the number of permutations.

Upvotes: 0

Views: 454

Answers (2)

Marcus
Marcus

Reputation: 6849

It seems like a bipartite graph maximum weight matching problem. The tricky part is how to construct the bipartite graph so that we can apply a polynomial time algorithm to solve the problem.

To make the problem easier, say we have 3 balls, and 2 buckets:

Ball 1: {1, 10},
Ball 2: {9, 20},
Ball 3: {7, 9};

Bucket 1: 2
Bucket 2: 1

and I would like to construct the graph like the following:

enter image description here

The main idea is to construct a bi-graph such that the left part of nodes stand for the Balls, while the other part are the buckets' nodes. And we give as many nodes as the capacity of each bucket, and now we can apply a maximum weight matching algorithm to solve our problem.

Upvotes: 5

Bathsheba
Bathsheba

Reputation: 234785

Because of the complexity, this is a type of problem that is best solved by an "what optimal result can I achieve in a fixed amount of time" approach. If you need the true global maximum than this will not work for you.

My first approach would be along the lines of simulated annealing:

1) Place the balls at random (subject to your at least one ball in each bucket constraint)

2) Compute the objective function (you must already have this from your brute force approach)

3) Consider operations like swapping two balls at random, moving one ball into another bucket (if the constraint allows).

4) Recompute the objective function

5) Always accept the change if the objective function is better, but also (and this is important), accept the change too if the objective function is worse with a probability that decays exp(-constant * time). (That's called the temperature function).

6) Go round again.

This approach will allow good buckets to stick together and, in early stages, allow the state to bounce away from a local maximum. The science here is to figure out a good value for 'constant'.

See http://en.wikipedia.org/wiki/Simulated_annealing

Upvotes: 2

Related Questions