[Solved] reaching the goal number [closed]

by


I would take a dynamic-programming approach:

def fewest_items_closest_sum_with_repetition(items, goal):
    """
    Given an array of items
      where each item is 0 < item <= goal
      and each item can be used 0 to many times

    Find the highest achievable sum <= goal

    Return any shortest (fewest items) sequence
      which adds to that sum.
    """
    assert goal >= 0, "Invalid goal"
    # remove any duplicate or invalid items
    items = set(item for item in items if 0 < item <= goal)
    # sort descending (work with largest values first)
    items = sorted(items, reverse=True)

    # start with the no-item sequence
    best   = {0: []}
    active = {0: []}
    # while we have further seeds to work from
    while active:
        nactive = {}
        for item in items:
            for total, seq in active.items():
                # find next achievable sum
                ntotal = total + item
                # if it is a valid subgoal and has not already been found
                if (ntotal <= goal and ntotal not in best):
                    # save it
                    best[ntotal] = nactive[ntotal] = [item] + seq
                    if ntotal == goal:
                        # best possible solution has been found!
                        break
        active = nactive

    # return the best solution found
    return best[max(best)]

which then runs like

>>> fewest_items_closest_sum_with_repetition([2,3,4,7,20,25], 105)
[25, 20, 20, 20, 20]

>>> fewest_items_closest_sum_with_repetition((40,79), 80)
[40, 40]

solved reaching the goal number [closed]