CODEWITHSUNDEEP
algorithmmathdistribution
Igneous01
Igneous01

Reputation: 739

Distribute Numbers So That Each Bucket Is Relatively Even

I'm working on some aspect of my game involving a depot. I'm trying to write a Resupply(stock) method so that it will resupply this depot object so that each resource in the depot is as evenly distributed as possible.

The depot has a finite maximum capacity (meaning it should not be possible to overstock a depot beyond its capacity). The depot defines a finite set of resources, that have a quantity (the number of items), as well as a multiplier (ie. You can have 4 units of Wood, but because of their large size they have a multiplier of 2, making the 4 units take up 8 units of space overall)

Take this example of a depot:

Depot A has a maximum capacity of 100, and it's current capacity is 50 (so 50% full)

There are 4 types of resources in this depot

A: 4 Units, Multiplier of 4     - (4 * 4) / 100 = 16%
B: 3 Units, Multiplier of 3     - (3 * 3) / 100 = 9%
C: 15 Units, Multiplier of 1    - (15 * 1) / 100 = 15%
D: 5 Units, Multiplier of 2     - (5 * 2) / 100 = 10%

Now say I wish to restock this depot by giving it 25 new units (these units are magical and for gameplay purposes can allocate themselves to any resource bucket).

How would I best distribute these 25 points so that the allocation of resources A,B,C,D are more or less equal to each other?

Lets say for a first pass we add 2 Units to B, and 3 Units to D:

B: Add 2 Units - (3 + 2) * 3    - 15 / 100 = 0.15
D: Add 3 Units - (5 + 3) * 2    - 16 / 100 = 0.16

After giving 5 units away, A,B,C,D share almost the same amount of storage in the depot. (16%,15%,15%,16%)

How would I achieve this:

Upvotes: 1

Views: 723

Answers (1)

user3386109
user3386109

Reputation: 34829

I'd go with a simple greedy algorithm:

  • ignore any resource that cannot be increased without exceeding the depot capacity
  • of the remaining resources find the one taking the least amount of space
    • if there's a tie, choose the resource with the smaller multiplier
  • add 1 unit to that resource type
  • repeat until all new units are used or none of the resources can be increased

Here's how the algorithm proceeds with the given example:

      -  B  D  D  B  D  C  B  C  D  A  C  C  D  B  C  C  D  A  C  B  C  D  C  C  D
4 A  16 16 16 16 16 16 16 16 16 16 20 20 20 20 20 20 20 20 24 24 24 24 24 24 24 24
3 B   9 12 12 12 15 15 15 18 18 18 18 18 18 18 21 21 21 21 21 21 24 24 24 24 24 24
1 C  15 15 15 15 15 15 16 16 17 17 17 18 19 19 19 20 21 21 21 22 22 23 23 24 25 25
2 D  10 10 12 14 14 16 16 16 16 18 18 18 18 20 20 20 20 22 22 22 22 22 24 24 24 26

Upvotes: 2

Related Questions