Say I have a set containing positive integers, and a target number m. Is there an algorithm that finds the shortest way (using the least numbers) by adding them to each other to reach m? Each number in the set can be used more than once.

For example, if the set is {1, 2} and the target number is 7, the shortest way is 2 2 2 1, which has a length of 4 (instead of something like 2 2 1 1 1, which has a length of 5)

I have already tried to code an algorithm to do this, but it is extremely slow. Here is the code I have:

import itertools


def can_make_sum(target, numbers_to_use):
    numbers = [False] * (target   1)  # numbers[i] stores False if i cannot be made with numbers_to_use, or a tuple
    # storing its factors with the smallest multiplier
    for number in numbers_to_use:
        multiplier = 1
        while True:
            product = multiplier * number
            if product > target:
                break
            if not numbers[product]:  # If the value is False
                numbers[product] = (number, multiplier)
            else:
                if numbers[product][1] > multiplier:  # only replace the multiplier if it is smaller than the previous
                    numbers[product] = (number, multiplier)  # multiplier, so it is the shortest way to make that number

            multiplier  = 1

    usable_numbers = []
    for product in numbers:
        if product != False:
            for _ in range(product[1]):
                usable_numbers.append(product[0])

    answer = []  # Final answer

    for i in range(1, len(numbers)):
        subsets = list(itertools.combinations(usable_numbers, i))  # All subsets of the usable numbers with length i
        for subset in subsets:
            total = sum(subset)
            if total == target:  # This is the smallest subset
                for num in subset:
                    for _ in range(numbers[num][1]):
                        answer.append(numbers[num][0])

                return answer


print(can_make_sum(13, {1, 2, 3}))

Just trying to make 13 with these three numbers already creates a noticeable delay before the answer comes out. Could this be improved and a lot faster, or is this already the fastest method?

CodePudding user response：

Just do an A* search. The nodes of our graph are (current_sum, smallest_number_used). Each will connect with what you get if you add another number that is at most smallest_number_used in size. Each edge has weight 1. And the heuristic we use is that the distance to the end is at least math.ceil(distance_left / smallest_number_used).

Here is code, along with several test cases. I cheated a little, but the idea is the above.

import heapq
import math

def can_make_sum(target, numbers_to_use):
    numbers = list(reversed(sorted(numbers_to_use)))
    visited = set()
    to_explore = [(0, 0, 0, 0, None)]
    while 0 < len(to_explore):
        min_final_steps, current_steps, current_value, min_i, path = heapq.heappop(to_explore)
        key = (current_value, min_i)
        if key not in visited:
            visited.add(key)
            if current_value == target:
                answer = []
                while path is not None:
                    answer.append(path[0])
                    path = path[1]
                return answer

            next_value = current_value   numbers[min_i]
            if next_value <= target:
                next_steps = current_steps   1
                heapq.heappush(
                    to_explore,
                    (
                       next_steps   math.ceil((target - next_value) / numbers[min_i]),
                       next_steps,
                       next_value,
                       min_i,
                       [numbers[min_i], path],
                    ))

            if min_i   1 < len(numbers):
                heapq.heappush(
                    to_explore,
                    (
                       current_steps   math.ceil((target - current_value) / numbers[min_i   1]),
                       current_steps,
                       current_value,
                       min_i   1,
                       path,
                    ))

print(can_make_sum(13, [1, 2, 3]))
print(can_make_sum(7, [1, 2]))
print(can_make_sum(100, [90, 9, 5]))
print(can_make_sum(30, [17, 15, 1]))
print(can_make_sum(26, [17, 15, 4]))
print(len(can_make_sum(1234567, [25, 15, 4])))