numbers - 如何检查一个数字是否可以表示为一些给定数字的总和

Question

我有一些整数的列表，例如[1, 2, 3, 4, 5, 10] 我还有另一个整数 ( N)。例如，N = 19。

我想检查我的整数是否可以表示为列表中任意数量的数字的总和：

19 = 10 + 5 + 4

或者

19 = 10 + 4 + 3 + 2

列表中的每个数字只能使用一次。N最多可以筹集到2000或更多。列表的大小可以达到 200 个整数。

有没有解决这个问题的好方法？

Answer 1

蛮力方法需要生成 2^(array_size)-1 个子集以求和并与 target 进行比较N。

只需将问题一分为二，就可以显着提高运行时间。以集合的形式存储数组的一半和另一半的所有可能总和。现在可以通过检查一组中的每个数字来确定n补码是否存在于另一组中N。n

这种优化将复杂性降低到大约：2^(array_size/2)-1+2^(array_size/2)-1=2^(array_size/2 + 1)-2 原来的一半。

这是一个使用这个想法的 c++ 实现。

#include <bits/stdc++.h>
using namespace std; 
bool sum_search(vector<int> myarray, int N) {
        //values for splitting the array in two
        int right=myarray.size()-1,middle=(myarray.size()-1)/2;

        set<int> all_possible_sums1,all_possible_sums2;

        //iterate over the first half of the array
        for(int i=0;i<middle;i++) {
            //buffer set that will hold new possible sums
            set<int> buffer_set;

            //every value currently in the set is used to make new possible sums
            for(set<int>::iterator set_iterator=all_possible_sums1.begin();set_iterator!=all_possible_sums1.end();set_iterator++) 
                buffer_set.insert(myarray[i]+*set_iterator);

            all_possible_sums1.insert(myarray[i]);

            //transfer buffer into the main set
            for(set<int>::iterator set_iterator=buffer_set.begin();set_iterator!=buffer_set.end();set_iterator++) 
                all_possible_sums1.insert(*set_iterator);
        } 

        //iterator over the second half of the array
        for(int i=middle;i<right+1;i++) {
            set<int> buffer_set;    

            for(set<int>::iterator set_iterator=all_possible_sums2.begin();set_iterator!=all_possible_sums2.end();set_iterator++)   
                buffer_set.insert(myarray[i]+*set_iterator);

            all_possible_sums2.insert(myarray[i]);

            for(set<int>::iterator set_iterator=buffer_set.begin();set_iterator!=buffer_set.end();set_iterator++) 
                all_possible_sums2.insert(*set_iterator);
        }

        //for every element in the first set, check if the the second set has the complemenent to make N
        for(set<int>::iterator set_iterator=all_possible_sums1.begin();set_iterator!=all_possible_sums1.end();set_iterator++)  
            if(all_possible_sums2.find(N-*set_iterator)!=all_possible_sums2.end()) 
                return true;                                       
        return false;
}

Answer 2

4 年半之后，乔纳森回答了这个问题。我想在 Python 中发布两个实现（bruteforce 和 Jonathan 的）及其性能比较。

def check_sum_bruteforce(numbers, n):
    # This bruteforce approach can be improved (for some cases) by
    # returning True as soon as the needed sum is found;

    sums = []

    for number in numbers:
        for sum_ in sums[:]:
            sums.append(sum_ + number)

        sums.append(number)

    return n in sums


def check_sum_optimized(numbers, n):
    sums1, sums2 = [], []
    numbers1 = numbers[:len(numbers) // 2]
    numbers2 = numbers[len(numbers) // 2:]

    for sums, numbers_ in ((sums1, numbers1), (sums2, numbers2)):
        for number in numbers_:
            for sum_ in sums[:]:
                sums.append(sum_ + number)

            sums.append(number)

    for sum_ in sums1:
        if n - sum_ in sums2:
            return True

    return False


assert check_sum_bruteforce([1, 2, 3, 4, 5, 10], 19)
assert check_sum_optimized([1, 2, 3, 4, 5, 10], 19)

import timeit

print(
    "Bruteforce approach (10000 times):",
    timeit.timeit(
        'check_sum_bruteforce([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 200)',
        number=10000,
        globals=globals()
    )
)

print(
    "Optimized approach by Jonathan (10000 times):",
    timeit.timeit(
        'check_sum_optimized([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 200)',
        number=10000,
        globals=globals()
    )
)

输出（浮点数是秒）：

Bruteforce approach (10000 times): 1.830944365834205
Optimized approach by Jonathan (10000 times): 0.34162875449254027

Answer 3

丑陋和蛮力的做法：

 a = [1, 2, 3, 4, 5, 10]
 b = []
 a.size.times do |c|
    b << a.combination(c).select{|d| d.reduce(&:+) == 19 }
 end
 puts b.flatten(1).inspect