列表中值的最大非连续和小于或等于k

Question

我有一个值列表[6,1,1,5,2]和一个值k = 10。我想从列表中找到小于或等于k的最大值之和，返回值和使用的数字。在这种情况下，输出将是：10，[6,1,1,2]

我使用了this code from GeeksForGeeks作为示例，但它不能正常工作（在本例中，代码的结果是9）

这些值不需要是连续的-它们可以是任意顺序

def maxsum(arr, n, sum):
    curr_sum = arr[0]
    max_sum = 0
    start = 0;

    for i in range(1, n):
        if (curr_sum <= sum):
            max_sum = max(max_sum, curr_sum)

        while (curr_sum + arr[i] > sum and start < i):
            curr_sum -= arr[start]  
            start += 1

        curr_sum += arr[i]  

    if (curr_sum <= sum): 
        max_sum = max(max_sum, curr_sum)  

    return max_sum 

if __name__ == '__main__': 
    arr = [6, 1, 1, 5, 2]  
    n = len(arr)  
    sum = 10

print(maxsum(arr, n, sum))

我还没有弄清楚如何将用于求和的值作为列表输出

Answer 1

下面是一个使用itertools.compositions的解决方案。对于小的列表来说，它足够快，但是如果您有一个大的总和和一个大的值列表，它会显著减慢

from itertools import combinations

def find_combo(values, k):
    for num_sum in range(k, 0, -1):
        for quant in range(1, len(values) + 1):
            for combo in combinations(values, quant):
                if sum(combo) == num_sum:
                    return combo

values = [6, 1, 1, 5, 2]
k = 10
answer = find_combo(values, k)
print(answer, sum(answer))

此解决方案适用于列表中的任何值和任何k，只要解决方案和中所需的值的数量不会变大

user10987432提供的解决方案有一个此函数可以避免的缺陷，即它总是接受将总和保持在k以下的值。对于该解决方案，值从最大值到最小值排序，然后迭代并添加到解决方案中，如果它没有使总和大于k。然而，一个简单的例子表明这是不准确的：
values = [7, 5, 4, 1] k = 10
在该解决方案中，总和将从0开始，然后随着第一个项目上升到7，在达到最后一个索引后在8结束。然而，正确的解决方案是5+4+1=10

Answer 2

这个问题至少和研究得很好的subset sum problem一样难，也就是NP-complete。特别是，任何解决问题的算法都可以用来解决子集和问题，方法是找到最大和<= k，然后如果和等于k，则输出True，如果和小于k，则输出False

这意味着您的问题是NP-hard，并且没有已知的算法可以在多项式时间内解决它。您的算法的运行时间在输入数组的长度上是线性的，因此它无法正确地解决问题，并且没有类似的算法能够正确地解决问题

一种可行的方法是backtracking search-对于每个元素，尝试将其包含在总和中，然后回溯并尝试不将其包含在总和中。这将花费输入数组长度的指数时间

如果数组元素总是整数，另一个选项是dynamic programming；有一个standard dynamic programming algorithm可以在伪多项式时间内解决整数子集和问题，它可以很容易地适应于解决您的问题形式