总和小于给定总和的最大子集 [英] Largest Subset whose sum is less than equal to a given sum

问题描述

列表的定义如下:[1, 2, 3]

及其子列表为:

[1], [2], [3],  
[1,2]  
[1,3]
[2,3]  
[1,2,3]

以K为例3，任务是找到元素总数之和小于k的子列表的最大长度.

Given K for example 3 the task is to find the largest length of sublist with sum of elements is less than equal to k.

我知道python中的itertools，但是它将导致较大列表的分段错误.还有其他有效的算法可以实现这一目标吗?任何帮助，将不胜感激.

I am aware of itertools in python but it will result in segmentation fault for larger lists. Is there any other efficient algorithm to achieve this? Any help would be appreciated.

我的代码允许:

from itertools import combinations
def  maxLength(a, k):
#print a,k
l= []

i = len(a)
while(i>=0):
    lst= list(combinations(sorted(a),i))
    for j in lst:
        #rint list(j)
        lst = list(j)
        #print sum(lst)
        sum1=0
        sum1 = sum(lst)
        if sum1<=k:
            return len(lst)
    i=i-1

推荐答案

您可以使用

You can use the dynamic programming solution that @Apy linked to. Here's a Python example:

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

ITEMS = [5, 4, 1]
for i in range(sum(ITEMS) + 1):
    print('{} -> {}'.format(i, largest_subset(ITEMS, i)))

输出:

0 -> 0
1 -> 1
2 -> 1
3 -> 1
4 -> 4
5 -> 5
6 -> 6
7 -> 6
8 -> 6
9 -> 9
10 -> 10

如果可以从items[0...j-1]中选择设置为i的值，则arr[i][j]中的arr[i][j]是True.自然，由于可以选择空集，因此arr[0]仅包含True值.同样，对于所有连续的行，第一个单元格为False，因为不能设置非零值的空集.

In above arr[i][j] is True if set with value of i can be chosen from items[0...j-1]. Naturally arr[0] contains only True values since empty set can be chosen. Similarly for all the successive rows the first cell is False since there can't be empty set with non-zero value.

对于其余单元格，有两种选择:

For rest of the cells there are two options:

1. 如果即使不考虑item[j-1]，已经有一个值为i的子集，则值为True
2. 如果有一个值为i - items[j - 1]的子集，那么我们可以向其中添加项目，并且有一个值为i的子集.

1. If there already is a subset with value of i even without considering item[j-1] the value is True
2. If there is a subset with value of i - items[j - 1] then we can add item to it and have a subset with value of i.

这篇关于总和小于给定总和的最大子集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！