0

I am currently learning Python and my idea would be to convert an existing Excel project into a web application.

As part of the configuration required in the project the user requires licenses for certain features. Example, if there are a total of 17 users that require a feature, the licenses are available for 1 user, 5 users, 10 users, 20 users.

So to cater for the 17 users above I would require: 2 x 1 user 1 x 5 user 1 x 10 user

The configuration consists of over 400 different licenses.

Achieving the above is possible using IF, ELIF and ELSE and returning the remainder and then looping all over again until the remainder is 0.

I am sure there would be a more productive way to go about the above.

Any advise or how to go about wording this better in a search to do more research?

Your assistance is appreciated.

WWessels
  • 27
  • 6
  • 2
    Here at stack overflow, you have to try the problem yourself before we help you. We help with faulty code, not school projects :) – clearshot66 Dec 08 '18 at 15:36
  • 1
    Sounds like classical NP-complete Knapsack Problem, see https://en.wikipedia.org/wiki/Knapsack_problem. Or, in your case, Coin Change problem, which is some specific case of Knapsack problem https://en.wikipedia.org/wiki/Change-making_problem. There are many possible algorithms described, but as for today there is no universal answer here. Feel free to check out different options and implement the one suits your needs better – The Godfather Dec 08 '18 at 15:43
  • @The Godfather, thank you very much, I was not aware of the term "Knapsack Problem" or "Change Making Problem". This is very helpful and allows me to better research the problem. Thank you again. – WWessels Dec 08 '18 at 15:58
  • @WWessels If you find the answer helpful, please upvote it and mark it as "Accepted answer". Welcome! – The Godfather Dec 08 '18 at 16:03

2 Answers2

0

This is well-known Change-making problem, which is (weakly) NP-hard problem.

As for all problems of such kind, there are several algorithms depending on how good solution do you want to find (usually it's easy to find somehow good solution and hard to find the best solution). Feel free to do your own research and select the one that suits your needs best.

As showed in a few other answers on *Overflow/Exchange network like 1, 2, 3 there is criteria for a given coin system [4][5] when greedy algorithm is optimal (such systems are called canonical coin systems). For your case if you have 1, 5 and 10-user possible licenses, greedy algorithm is optimal.

[4] D. Pearson. A Polynomial-time Algorithm for the Change-Making Problem

[5] Xuan Cai and Yiyuan Zheng. Canonical Coin Systems for Change-Making Problems

The Godfather
  • 4,235
  • 4
  • 39
  • 61
  • 2
    Note, though, that the greedy algorithm is optimal for change-making if you have the right set of coins, of which 1-5-10 is an example. – chepner Dec 08 '18 at 16:05
  • @chepner I really went thru related questions and answers around, because I'd like to add it to my answer, but I was not able to find simple and understandable criteria of *right set of coins*\\*canonical coin system*. – The Godfather Dec 09 '18 at 12:29
  • I read the question more completely, and I now think "over 400 different licenses" makes this more than a simple change-making problem. I think you'd essentially have to read Cai and Zheng (which, to be honest, I haven't done) to understand their notion of "canonical coin system", which may not entirely apply to the OP's problem. If there are really 400 different licenses, I think they would have to be distinguished by more than simply how many users a single license applies to, so this is probably a more complicated optimization problem. – chepner Dec 09 '18 at 15:55
0

If lower tiers in the coinage divides the higher tiers, then it's easy to solve using a greedy algorithm.

def change_making(tiers, total):
    for tier in sorted(tiers, reverse=True):
        while tier <= total:
            yield tier
            total -= tier
    if total:
       raise ValueError(f'there\'s {total} left over')

>>> list(change_making([10, 5, 1], 17))
[10, 5, 1, 1]

As pointed in a comment, the greedy algorithm will produce non-optimal solutions in cases where lower tiers are not factors of higher tiers. Then you have to look into other knapsack / coin-making algorithms as suggested by other answers.

Håken Lid
  • 22,318
  • 9
  • 52
  • 67
  • "If there is a factor of at least 2"... - if I read and understand this correctly, this is not true. Having set of coins [1 40 100] (so each next coin is more than 2 times bigger than previous) and trying to make a change for 120. Greedy algorithm will use 100 and 20 more 1-cent coins. However optimal is three: 40+40+40. – The Godfather Dec 09 '18 at 12:33
  • @TheGodfather: Thanks for pointing that out. The greedy algorithm will not give the optimal solution in that case. I think instead each tier must be exactly divisible by every lower tier. – Håken Lid Dec 09 '18 at 12:48