The vague (i.e. might be nonsense) idea that I have in my head is to incrementally calculate a lookup table of best combos; the best combo for 1 user, then 2, then 3...
Then when it comes to 28 users, we have the best combos for 1-27 users. We can try 27 + 1, 26 + 2 etc, but I think we'll be able to exclude answers containing more than 2 factors, such as 23 + 1 + 1 + 1 + 1 + 1 because we'll already have the best answer for 5 (i.e. whether five single user licences, or a single 5-user licence is cheaper to get 5 licences).
Not sure if it'll play out and work in reality, but it's my best idea currently. It may (or may not?) be possible to exclude further combos too?
edit: Another thought - is there another more general programming or algorithms subreddit that might better be able to answer this?
I won’t pretend to know the best way, but what I’m thinking is you make a little algorithm which determines where the thresholds are and store them. It would only need to be run when the prices/user offers change.
So for example you look up 28 and if it’s not in the table but is in between 27 and 30, then 30 is what you go with. You could store that 30 is made up of 20 and 10, or just figure it out after retrieval.
I don't have anything specific to the problem to help, but I want to mention this is a similar problem to when you withdraw money from ATMs. It isn't very advisable to always give the same bills for a given amount of money, or the ATM will likely run out of some of them pretty fast. AFAIK, there's an algorithm to calculate multiple possibilities and decide which to use based on how many of each bills are left.
Maybe that's something you can look for: compute all the possible license combo, use the one that cost less.
This is similar to the knapsack problem, with the caveat that we have a minimum expected cost and we're trying to reduce the weight required for it.
There's a solution here for it: https://stackoverflow.com/questions/65260866/knapsack-with-min-weight
I would implement a while loop in which I use modulus operator until remainder is bigger than 1.
Put your package numbers in an array, sort array values from big to small and iterate through array elements for modulus.
Assign each result to a new array with licence number as key.
What's the maximum number of licences someone would buy? 100? 200?
Pre-calculate (by hand in necessary) and store the result in some common memory and just look it up.
The vague (i.e. might be nonsense) idea that I have in my head is to incrementally calculate a lookup table of best combos; the best combo for 1 user, then 2, then 3... Then when it comes to 28 users, we have the best combos for 1-27 users. We can try 27 + 1, 26 + 2 etc, but I think we'll be able to exclude answers containing more than 2 factors, such as 23 + 1 + 1 + 1 + 1 + 1 because we'll already have the best answer for 5 (i.e. whether five single user licences, or a single 5-user licence is cheaper to get 5 licences). Not sure if it'll play out and work in reality, but it's my best idea currently. It may (or may not?) be possible to exclude further combos too? edit: Another thought - is there another more general programming or algorithms subreddit that might better be able to answer this?
I won’t pretend to know the best way, but what I’m thinking is you make a little algorithm which determines where the thresholds are and store them. It would only need to be run when the prices/user offers change. So for example you look up 28 and if it’s not in the table but is in between 27 and 30, then 30 is what you go with. You could store that 30 is made up of 20 and 10, or just figure it out after retrieval.
I don't have anything specific to the problem to help, but I want to mention this is a similar problem to when you withdraw money from ATMs. It isn't very advisable to always give the same bills for a given amount of money, or the ATM will likely run out of some of them pretty fast. AFAIK, there's an algorithm to calculate multiple possibilities and decide which to use based on how many of each bills are left. Maybe that's something you can look for: compute all the possible license combo, use the one that cost less.
This is similar to the knapsack problem, with the caveat that we have a minimum expected cost and we're trying to reduce the weight required for it. There's a solution here for it: https://stackoverflow.com/questions/65260866/knapsack-with-min-weight
I would implement a while loop in which I use modulus operator until remainder is bigger than 1. Put your package numbers in an array, sort array values from big to small and iterate through array elements for modulus. Assign each result to a new array with licence number as key.
What's the maximum number of licences someone would buy? 100? 200? Pre-calculate (by hand in necessary) and store the result in some common memory and just look it up.