数组中的总和不大于 k

Question

给定一个整数数组和一个整数 k

从给定数组中查找小于或等于 k

的最大可能总和

• 示例：

  数组 = 7,6,9,11 k = 25

• 答案：

  24

• 说明：

  可能的组合：
  尺寸 1 = (7),(6),(9),(11)
  尺寸 2 = (6,7), (6,9), (6,11), (7,9), (7,11), (9,11)
  尺寸 3 = (6,7,9), (6,7,11), (6,9,11), (7,9,11)
  尺寸 4：（6,7,9,11）

  在这些可能的组合中，最大且小于或等于 k=25 的项之和为 (6,7,11)=24

• 限制：

  数组的大小为1到40
  k 的值为 1 到 10⁹
  数组中项目的值为 1 到 10⁹

我正在使用post中提到的代码：

def largest_subset(items, k):
    res = 0

    # We can form subset with value 0 from empty set,
    # items[0], items[0...1], items[0...2]
    arr = [[True] * (len(items) + 1)]

    for i in range(1, k + 1):
        # Subset with value i can't be formed from empty set
        cur = [False] * (len(items) + 1)

        for j, val in enumerate(items, 1):
            # cur[j] is True if we can form a set with value of i from
            # items[0...j-1]
            # There are two possibilities
            # - Set can be formed already without even considering item[j-1]
            # - There is a subset with value i - val formed from items[0...j-2]
            cur[j] = cur[j-1] or ((i >= val) and arr[i-val][j-1])
        if cur[-1]:
            # If subset with value of i can be formed store
            # it as current result
            res = i

        arr.append(cur)
    return res

它适用于小范围的输入，但是当程序的输入很大时，代码会在以下行失败：

cur = [False] * (len(items) + 1)

说内存错误。

我还尝试了另一篇帖子

def subset_sum(vals, target=0):
    sums = {0: [()]}  # key=sum, value=list of subsets for the sum
    if target in sums:
        yield from sums[target]  # annoying base case
    for val in vals:
        items = sums.items()  # don't change dict size during iteration
        sums = dict(items)
        for prev_sum, prev_subsets in items:
            sum_ = prev_sum + val
            subsets = [s + (val,) for s in prev_subsets]
            sums[sum_] = sums.get(sum_, []) + subsets
            if sum_ <= target:
                yield from subsets

它也失败并出现相同的错误消息：

subsets = [s + (val,) for s in prev_subsets]

解决这个问题的正确方法是什么。

Answer 1

修改这个答案：不能由数组中的数字之和形成的最小数字

使用位向量来完成此操作。

从空位向量开始 b。然后对于数组中的每个元素 x，执行以下操作：

b = b | << x | 2^(x-1)

需要明确的是，第i个元素被设置为1来表示数字i，并且| x 将第 x 个元素设置为 1。

在执行上述步骤 (b = b | ...) 时，在 k 位之后截断修改后的 b，因为我们不关心生成更大的值。

处理完数组后，b 中某个集合位的最大索引就是您的答案（从右数，从 1 开始）。

在此示例中，对于 [4,13,2,3,1]，我们可以将除 11 和 12 之外的所有值设置为 23。

b=0 过程4：b = b | <<4 | 1000 = 1000 process 13: b = b | b<<13 | 1000000000000 = 10001000000001000 process 2: b = b | b<<2 | 10 = 1010101000000101010 process 3: b = b | b<<3 | 100 = 1011111101000101111110 process 1: b = b | b<<1 | 1 = 11111111111001111111111 First zero: position 11.