python - 大于数字的唯一总和

Question

所以我正在尝试编写一个代码，该代码采用 1 到 10 之间的数字列表并找到大于或等于 10 的总和，然后从列表中删除这些数字。转折点是:首先您需要检查列表中是否有任何 10，是否有任何两个数字总和为 10，然后是任何 3 个数字，依此类推直到 5。此外，数字总和越小越好。因此，在对夫妇求和时，您需要去掉大部分数字。到目前为止，我设法做了这对夫妇:

n = input("How many numbers in the list? \n")
throw = []
for i in range(int(n)):
    throw.append(random.randint(1, 10))
throw.sort()
increments = 0
print(throw)
increments += throw.count(10)
throw = list(filter(lambda i: i != 10, throw))

high = len(throw)-1
low = 0
acceptable_couples = []
get_rid = []
while low < high:
    sums = throw[high] + throw[low]
    if sums >= 10:
        increments += 1
        get_rid.append(throw[high])
        get_rid.append(throw[low])
        acceptable_couples.append((throw[high], throw[low]))
        high -= 1
        low += 1
    else:
        low += 1
for i in get_rid:
    throw.remove(i)

我也做了一对 3 并且正在考虑对 4 和 5 应用相同的方法:

 while len(throw) >= 3:
    z = 0
    x = list(itertools.combinations(throw, 3))
    for couple in x:
        if sum(couple) >= 10:
            z += 1
            i = list(couple)
            increments += 1
            for j in couple:
                throw.remove(j)
            break
        else:
            continue
    if z == 0:
        break

我希望找到一种不那么困惑的方法来做到这一点。这行得通，但对于大量数字来说，似乎有很多无用的计算。有什么想法吗？

Answer 1

在那种情况下，也许这是一个解决方案。在伪代码中:

1. 读取数字列表并从高到低排序
2. 从列表中删除所有数字 10 并将它们添加为解决方案
3. 循环直到列表为空
4. 取出列表中最大的数字(即列表排序后的第一个数字)并将其从列表中删除
5. 检查通过添加最小的数字是否可以得到大于或等于 10 的总和，如果在我们完成循环之前不能得到更大的数字。如果找到解决方案，则中断循环，将其添加到解决方案并从列表中删除解决该问题的元素。
6. 如果解决了，中断并用列表中的下一个最大数字重复外部 while 循环。如果没有解决，则将下一个最大的数字添加到总和并将其从列表中删除，并检查我们是否可以找到解决方案添加较小的数字再次运行 for 循环

代码

import random

n = int(input("How many numbers in the list? \n"))
throw = [random.randint(1, 6) for _ in range(n)]
print(throw)

throw.sort(reverse=True)
print(throw)

list_of_solved_sets = []

# remove all numbers 10 from the list and add a solution
while throw and throw[0] == 10:
    list_of_solved_sets.append([throw[0]])
    del throw[0]

while throw:

    # take the largest number in the set (which is the first number 
    # as list is sorted) and remove it from the list
    solved_set = [throw[0]]
    _sum = throw[0]
    del throw[0]

    while throw:
        solved = False

        # Check if by adding the smallest number we can get
        # a sum greater or equal to 10 if not go to a bigger number
        # until we complete the loop. Break loop if a solution is found, add
        # to solutions and remove element from the list that solved it
        for j in range(len(throw) - 1, -1, -1):
            if _sum + throw[j] >= 10:
                solved_set.append(throw[j])
                del throw[j]

                list_of_solved_sets.append(solved_set)

                solved = True
                break

        # if solved break and repeat the outer while loop with next biggest number
        # in the list. If not solved then add the next biggest number to the sum and      
        # check if we can find a solution adding smaller numbers running the for 
        #loop again
        if solved:
            break

        else:
            _sum += throw[0]
            solved_set.append(throw[0])
            del throw[0]

print('List of solved sets:')
for i, solved_set in enumerate(list_of_solved_sets):
    print(f'   {i+1}: {solved_set}')

结果示例:

How many numbers in the list?
10
[3, 2, 5, 1, 6, 3, 4, 3, 2, 1]
[6, 5, 4, 3, 3, 3, 2, 2, 1, 1]
List of solved sets:
   1: [6, 4]
   2: [5, 3, 2]
   3: [3, 3, 2, 1, 1]