达到目标数

Question

我是初学者所以如果这个问题听起来stupid/unclear或者很简单，请耐心等待。

如何将数字列表加在一起以达到目标数字或尽可能接近目标数字？例如，这里有一个数字列表：(2,3,4,7,20,25)，目标 = 105。结果应该是这样的：(25,25,25,25,3,2)。给定数字的顺序很重要；始终从列表中最大的数字开始并将它们相加以接近给定值，因此它将选择下一个要测试的数字。结果也可能是 (20, 20, 20, 20, 25)，这在这种情况下是不正确的，因为它不遵循数字的顺序。该算法只有在可以跳的情况下才跳到下一个数字，否则不能跳。

最好的 M

Answer 1

l=(2,3,4,7,20,25)
goal = 105

a=max(l)
b=0
res=[]
while b<=goal-24:
    b+=a
    t=goal-b
    res.append(a)
    g=0
    for x in l:
        g+=x
        if g==t:
            res.append(x)
            res.append(g-x)
            break

print (res)

输出：

>>> 
[25, 25, 25, 25, 3, 2]
>>>

我找到了这个解决方案，但是，真的让我很恼火:-)！棘手的部分是 while b<=goal-24: ，其他代码是基本的 Python.

Answer 2

这样对吗？我现在没时间测试。

def solution(numbers, goal):
    curr = 0
    numbers = sorted(numbers)
    while curr < goal:
        if not numbers: break
        n = numbers.pop()
        while n + curr <= goal:
            yield n
            curr += n

list(solution([2,3,4,7,20,25], 105))

结果：

[25, 25, 25, 25, 4]

Answer 3

如果速度不是问题，这里是最终正确的回应：

import itertools

def change_maker(coins, amount):
    for r in range(amount//max(coins), amount//min(coins)+1):
        possibilities = (combo for combo in itertools.combinations_with_replacement(coins, r) if sum(combo) == amount)
        try:
            result = next(possibilities)
        except StopIteration:
            # no solution with current r
            continue
        else:
            return result

这总是 return 最佳结果，但在某些情况下可以计算出一个荒谬的组合数。

演示：

>>> coins = (2, 3, 4, 7, 20, 25)
>>> goals = 105
>>> print(change_maker(coins, goal))
[20, 20, 20, 20, 25]

Answer 4

我会采用动态规划方法：

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)]

然后像

一样运行

>>> 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]

达到目标数

reaching the goal number

python

numbers