CODEWITHSUNDEEP
algorithmsorting
spamup
spamup

Reputation: 466

How to find the closest set of numbers from a given one?

I am trying to find a proper algorithm for the following task:

I have an amount of resources (actual available quantity). This amount increases constantly at a given rate (increase/min). The goal is to buy all available products from all given options a,...,n (here: option_A, option_B, Option_C).

Now, depending on the rising resources, which product can be bought earlier (here: option_A4, option_B3, option_C3)?

Actual available quantity                   
Resource A  142             
Resource B  56              
Resource C  383             
Resource D  335             

Increase/min                    
Resource A  2               
Resource B  263             
Resource C  482             
Resource D  301             

Option_A    ResA    ResB    ResC    ResD    bought
Product 1   00032   00066   00058   00008   *
Product 2   00292   00395   00407   00024   *
Product 3   01752   03555   02033   00073   *
Product 4   03505   31999   12200   00294   
Product 5   07009   63998   85401   02938   

Option_B    ResA    ResB    ResC    ResD    bought
Product 1   00008   00048   00006   00034   *
Product 2   00049   00240   00012   00134   *
Product 3   00098   01438   00083   00806   
Product 4   00491   04314   00499   06451   
Product 5   03929   08628   04985   12901   

Option_C    ResA    ResB    ResC    ResD    bought
Product 1   00022   00011   00024   00078   *
Product 2   00111   00106   00122   00699   *
Product 3   00334   00211   00610   04892   
Product 4   00669   01477   01831   39137   
Product 5   06020   04432   16482   78275

I don't know if there is an algorithm for solving this kind of tasks already out there, but my approaches would be:

Approach A
1. Sum of digits of the actual available quantity
2. Sum of digits of every product
3. Compare the sum of the actual available quantity with each sum of products
4. Identify the product with the less distance

This would be easy, but it pictures only the actual situation without involvement of the constantly rising resources.

Approach B
1. Calculate how long it would take, to reach every single resource depending of the actual amount of resources plus the increasing rate.

E.g. for Option_A, Product 1, ResA:
needed: 3505
available: 142
increase: 2/min
required: 3363 (3505-142)
time after reaching requirements: 1681,5min (3363/2)
2. Repeat for ResB,ResC,ResD and sum the amount of time
3. Repeat 1+2 for every product
4. Choose the product with the shortest amount of time

What do you think?

Upvotes: 1

Views: 188

Answers (1)

justhalf
justhalf

Reputation: 9117

Looks like you're building a script for resource management game like C&C Tiberium Alliances, haha

My answer would be: your second approach is the way, with a few alterations.

On your second step, you don't sum the amount of time, instead you pick the maximum of them. This is because all the resources are increasing concurrently, right?

See this example:

            Res A   Res B   Res C   Res D
Current       142      56     383     335
Increment       2     263     482     301

Product 4    3505   31999   12200     294
Required     3353   31943   11817       0
Time       1676.5   121.5    24.5       0 mins

So you need 1676.5 mins until Res A is enough to buy Product 4 (of Option A), 121.5 mins for Res B, 24.5 min for Res C, and none for Res D as it's already enough.

The time you need to actually be able to buy Product 4 will be 1676.5 mins (i.e., the maximum)

Then you repeat that for every product not bought yet, then sort with increasing time left.

Hope this helps!

Upvotes: 2

Related Questions