小于给定值的最大子集合和

-2

给出一个整数和数字k的数组。问题是找到一个子集，使得总和最大并小于给定数量k。我觉得有一个动态的编程方法来解决这个问题，但我不知道如何有效地解决这个问题。小于给定值的最大子集合和

2017-01-22 guser

什么是对数组元素和数组大小的约束？ –

元素是小于10000的正整数。数组大小小于1000 – guser

如果K不是太大，可以使用通常的背包方法。 –

这类问题的简单动态程序都使用相同的基本技巧：对于数组的每个连续前缀，计算其子集总和的集合，这取决于以下事实：当输入元素有界时，集有很多少于2^n个元素（对于所讨论的问题，小于10,000,000而不是2^1000）。 Python中的这个特殊问题：

def maxsubsetsumlt(array, k): 
    sums = {0} 
    for elem in array: 
     sums.update({sum_ + elem for sum_ in sums}) 
    return max(sum_ for sum_ in sums if sum_ < k)

来源

2017-01-22 17:48:10

小于给定值的最大子集合和

回答

相关问题