Algorithm using a combination of numbers to achieve a target or exceed it in the most efficient way-CodePudding

I am looking into a problem given a list and a target. I can use any number in the list multiple times to achieve the target or slightly exceed it. It needs to be the most efficient combo. The ones I have been finding try to hit the target and if they can't then we return nothing.

For example, if I have a target of 242 and a list of 40,and 100, 240.

the most efficient would be to use 40 four times and 100 once. That gives us 260.

I tried going down the approach of using remainders. I would start with the largest number, see what remains

Just going down the algo first (not the most efficient way)

242 % 240 --> Quotient: 1, Remainder: 2--> So Use 240 240 = 480.

242 % 100 --> Quotient: 2, Remainder: 42 --> Use 100, 100, 100 = 300 --> Better

242 % 40 --> Quotient: 6, Remainder: 2 --> Use 6*40 40 = 280 --> Even better.

Try to use a combo

242 % 240 --> Remainder is 2. Try using the next smallest size. 240 100 --> 340. Bad

242 % 100 --> Remainder is 42. Try using the next smallest size. 40 40. 100 100 40 40. 280. Better.

Last case doesn't matter.

None of these work. I need to determine that 100 40 40 40 40 = 260. This would be the best.

Do I need to go through every combination of potential values? Any direction would be helpful.

CodePudding user response：

Here is a solution using A* search. It is guaranteed to find the path to the smallest amount over, using the least coins, in polynomial time. If a greedy solution works, it will get there very quickly. If it has to backtrack, it will backtrack as little as it needs to.

Note the k hack is to break all comparisons from heapq.heappush. In particular we never would want to wind up comparing down to the potential trailing None at the end (which would be a problem).

import heapq
from collections import namedtuple

def min_change (target, denominations):
    denominations = list(reversed(sorted(denominations)))

    k = 0

    CoinChain = namedtuple('CoinChain', ['over', 'est', 'k', 'coins', 'value', 'i', 'prev'])
    queue = [CoinChain(0, target/denominations[0], k, 0, 0, 0, None)]
    found = {}
    while True: # will break out when we have our answer.
        chain = heapq.heappop(queue)
        if target <= chain.value:
            # Found it!
            answer = []
            while chain.prev is not None:
                answer.append(denominations[chain.i])
                chain = chain.prev
            return list(reversed(answer))
        elif chain.value in found and found[chain.value] <= chain.i:
            continue # We can't be better than the solution that was here.
        else:
            found[chain.value] = chain.i # Mark that we've been here.
        i = chain.i
        while i < len(denominations):
            k = k 1
            heapq.heappush(
                queue,
                CoinChain(
                    max(chain.value   denominations[i] - target, 0),
                    chain.coins   1,
                    k,
                    chain.coins   1,
                    chain.value   denominations[i],
                    i,
                    chain
                )
            )
            i  = 1

print(min_change(242, [40, 100, 240]))

CodePudding user response：

This is actually kind of knapsack problem or "change-making" alghoritm: https://en.wikipedia.org/wiki/Change-making_problem

The change-making problem addresses the question of finding the minimum number of coins (of certain denominations) that add up to a given amount of money. It is a special case of the integer knapsack problem, and has applications wider than just currency.

Easy way to implement it is backtracking with these rules:

Add highest possible value to your solution
Sum up the values of your solution
If treshold was exceeded, replace the last highest value with lower one. If there is already lowest possible value, remove the value and lower the next value

Example:

current: [] = 0, adding 240
current: [240] = 240, adding 240
current: [240, 240] = 480, replacing with lower
current: [240, 100] = 340, replacing with lower
current: [240, 40] = 280, replacing with lower not possible. Remove and lower next value
current: [100] = 100. Adding highest
current: [100, 240] = 340. Replacing with lower
current: [100, 100] = 200. Adding highest
....

Eventually you get to [100,40,40,40,40] = 260

Just read about that there can be amount that cannot be achieved. I suppose those are the rules:

If the value can be achieved with coins, the correct solution is the exact value with lowest possible number of coins.
If value cannot be achieved, then the best solution is the one that exceeds it, but has lowest possible difference ( if there are more solutions with this same value, the one with lowest number of coins wins)

Then you just use what I wrote, but you will also remember solutions that exceeded it. If you find solution that exceeded, you will persist it. If you find solution with better results (less exceeding or same value, but less coins), you replace it as your "best solution".

Also note that the first solution this alghoritm finds (if the number is achievable) is the best one and you can stop. As it is prioriting the highest values first, it finds the solution with smallest number of coins first.