Return 列表中等于 x 的最大子集或数字值

Question

我正在尝试 return 构成给定值总和的最大数字，如果列表中有一个数字构成该值 return 那

numberlist = [0,1,2,3,4,5,8,16,32,64,128]

def getSubsetOrSingle(x,listofvalues):
    if x in listofvalues:
        return x
    else:
        return list()# list of the biggest values available that make up x

我能够匹配列表中 x 的值，例如如果您要传递

getSubsetOrSingle(128, numberlist)

它将 return 你 128 但我想通过 208 并从列表中取回最大可能的值：

>>> print(getSubsetOrSingle(208, numberlist))
>>> [16,64,128]
>>> print(getSubsetOrSingle(128, numberlist))
>>> 128
>>> print(getSubsetOrSingle(33, numberlist))
>>> [1,32]
>>> print(getSubsetOrSingle(136, numberlist))
>>> [8,128]

Answer 1

我会把它分成两种情况来处理这个问题。检查目标数字是否完全等于输入列表中的任何元素的情况可能很容易实现。您正在查看的另一种情况可以通过一种很好的动态编程/记忆方法来解决。

让我们从一个慢速递归算法开始，然后我们可以将其转换为 DP 风格的递归。假设您想解决以下问题：

What is the maximum quantity of numbers you can use to sum up to some target number T using only the first k numbers from the list?

作为基本情况，如果 k = 0（也就是说，你开始使用零数），那么你可以使用零数使 T = 0，并且不可能以任何方式使 T > 0。我们将通过说您需要 -&infinity; 来表示这一点。这样做的数字表示这是不可能的。

现在，假设您有 k > 0 个数字要处理。在这种情况下，您有两种选择。一种选择是将第 k 个数字作为总数的一部分。如果该数字是 m，那么您将希望使用前 k - 1 个数字使用尽可能多的数字来形成 T - m。（你只能在 m ≤ T 时这样做。）另一种选择是不包括第 k 个数字，在这种情况下，你希望使用前 k - 1 个硬币中尽可能多的硬币来形成 T。

这里有一些粗略的伪代码。我假设向负无穷大添加任何东西都会返回负无穷大：

function mostNumbersFor(numberList, k, T) {
    /* Base case: if T < 0, we can’t make T. */
    if (T < 0) return -infinity;

    /* Base case: if k = 0, we can only make T = 0. */
    if (k == 0) {
        return T == 0? 0 : -infinity;
    }

    /* Otherwise, we either include the current number, or we don’t.
     * We take the better of the two options.
     */
    return max(mostNumbersFor(numberList, k - 1, T),
               mostNumbersFor(numberList, k - 1, T - numberList[k - 1]) + 1);
}

如果你再打电话

mostNumbersFor(numberList, numberList.length + 1, T);

您将获得最大数量的加起来恰好为 T 的数字。

现在，这种方法真的非常慢，因为它会进行各种重复的递归调用。但是，如果您添加记忆化或动态编程来消除那些冗余调用，速度会快很多。具体来说，k 只有 O(n) 个可能值（其中 n 是输入列表的长度），T 参数只有 O(W) 个可能值，其中 W 是输入目标值。这使得总运行时间为 O(nW)，它在 W 中是伪多项式的，对于 W 的小值在实践中可能非常快。

Return 列表中等于 x 的最大子集或数字值

Return largest subset or value of number from list that equals to x

recursion

memoization

dynamic-programming

subset-sum

python-3.x