3 ms·
An interesting meta problem is to determine antagonistic set of denominations, like the [10,9,1] example given in the post, to maximize the number of coins sele
by Jun8 1y ago
An interesting meta problem is to determine antagonistic set of denominations, like the [10,9,1] example given in the post, to maximize the number of coins selected by the gradient method.
- mgradowski 1y agoIsn't it trivially [1]?
- zahlman 1y agoPerhaps what is meant is "maximize the difference between the optimal result and the one calculated by the naive greedy algorithm".
- Jun8 1y agoThanks for clarifying my poorly worded description, that’s exactly what I meant. Like in the example given, the difference is 10-4=6, let’s call this the naive_greedy_miss_factor. Can we choose three other denominations so that NGMF is > 6?