找到最小数量的硬币，使给定的阵列

Question

问题所在

输入整数数组A，其中1<=A[i]<=1000000。

找到正整数多集S (就像硬币一样)的最小大小(基数)，这样对于每一个A[i]，都存在一个S的子集，其和等于A[i]。

example1

输入A = [1,27,28]。

输出2，最小的多集之一是{1,27}。

example2

输入A=[18,37,42,50]

输出3，唯一最小的多集是{5,13,37}

这个测试用例表明，min(A)没有出现在S中，答案> ceil(log2(len(A)))。

我的问题

即使是len(A)<=10，我也找不到任何正确和果断的算法。当len(A)约为10时，有什么解决方案有效吗？

我只能在len(A)<=6时找到一种有效的算法

例如，当len(A)==6时，从A中删除副本。假设S的大小为5，然后以时间复杂度O(perm(32，5))枚举所有可能的系数c00,c01,c02,c03,c04,c10,...(cij∈{0,1})，从而使∑(cij*S[j])==A[i] (0<=i<5)。在O(5^3)中用高斯消去法求解这五个线性方程组，再用背包算法对A[5]进行检验。如果没有解决方案，答案是6，否则S的大小最多为5。假设S的大小为4，再次重复前面的过程。直到找到正确的解决方案为止。

这样的问题(很难写，使用蛮力)有一些正式的术语吗？

Answer 1

在下面的回答中，我将考虑数组A，其中所有的值都是严格正的，并且数组中的值是唯一的。首先，我想首先说明比较明显的问题。

1. 如果数组A有2个数字，最小的数字集是2(集合A本身)如果数组A有3个数字，最小的数字集将是2当且仅当最小数之和等于第三个数，否则它将是3(集合A本身)

<代码>G 210

在注意到这一点之后，我想从相反的角度来看待这个问题，这将使我们对解决我们的问题有深刻的见解。给定一组n数，可以将所有2**n - 1不同的数字组合在一起，因为集合中的每个数字可以单独存在，也可以不在求和中。

示例

给出一组由三个数字组成的{a,b,c}，可以生成总共的2**3 - 1 = 7数字：

a，b，c，a+b，a+c，b+c，a+b+c

因此，我们可以在给定A长度的最小集数上导出一个下界，称为m。

Lower_bound = ceil(log2(m+1))

这意味着长度为4至7的A的下界为3，长度为8至15的下限为4，等等。

解决建议

这将提出一个解决方案的建议，它可能有一些缺陷，但它涵盖了我可以提出的大部分内容。

既然我们现在有了一个界，如果我们找到一个有界长的集来解决我们的问题，它就保证是最优的，结果应该是界。我建议以下解决方案

1. 表示ss在范围内(3，m)

1.1。获取2和ss-1之间的所有组合，检查每个组合的和是否在数组中。如果是，则从数组中移除和。

1.2。从A中的每个剩余值中减去其余的所有剩余值，创建一个对角线为0的对称矩形矩阵。

1.3。对于形成矩阵中两个正值的每一个可能组合，检查是否：

1.3.1。组合的和在A中。

1.3.2。A中的数字可以分解为两个数字，可以与A的其他成员一起添加。如果是，则从A中删除这三个数字，并将两个分解后的数字添加到中。

这方面的python实现如下：

from itertools import combinations
import numpy as np

def get_subset_count(A):
    m = len(A)
    if m == 2:
        return 2
    elif m == 3:
        return 3 if A[0] + A[1] == A[2] else 2
    else:
        lower_bound = int(np.ceil(np.log2(m + 1)))
        for ss in range(lower_bound, m): # checking if there is a subset with size of ss
            A_temp  = A.copy()
            removed = set()
            sub_values = []
            # phase 1 - looking if a summation of components in A result in other components in A
            for kk in range(2, ss+1):
                for comb in combinations(A[:ss+1, kk):
                    if sum(comb) in A_temp:
                        A_temp.remove(sum(comb))
                        removed.add(sum(comb))
            if len(A_temp) <= ss: return ss
            # phase 2 - looking for hidden base components
            deduction = np.array(A_temp)[:, None] - np.array(A_temp)
            for comb in combinations(deduction[deduction > 0].tolist(), 2):
                if sum(comb) in A_temp: # checking if the sum is in  the array
                    A_temp2 = A_temp.copy()
                    A_temp2.remove(sum(comb))
                    comb0_logic = [comb[0] + a in A_temp2 for a in A_temp2]
                    comb1_logic = [comb[1] + a in A_temp2 for a in A_temp2]
                    if any(comb0_logic) and any(comb1_logic): # checking if combination is a hidden base
                        A_temp.remove(sum(comb))
                        removed.add(sum(comb))
                        A_temp.remove(sum(comb[0] + np.array(A_temp2)[comb0_logic]))
                        removed.add(sum(comb[0] + np.array(A_temp2)[comb0_logic]))
                        sub_values = [comb[0]] + sub_values
                        if comb[0] + np.array(A_temp2)[comb0_logic] != comb[1] + np.array(A_temp2)[comb1_logic]:
                            A_temp.remove(sum(comb[1] + np.array(A_temp2)[comb1_logic]))
                            removed.add(sum(comb[1] + np.array(A_temp2)[comb1_logic]))
                        sub_values = [comb[1]] + sub_values
            if len(A_temp) + len(sub_values) <= ss: return ss
        return len(A)

使用以下方法运行此方法时：

A = [4,5,7,16]
print(get_subset_count(A))  # 3 - 4,5,7
A = [9,11,12,16]
print(get_subset_count(A))  # 3 - 4,5,7
A = [4,5,7,9,11,12,16]
print(get_subset_count(A))  # 3 - 4,5,7
A = [4,5,7,9,11,12,17]
print(get_subset_count(A))  # 4 - 4,5,7,17
A = [18,20,37,42,50]
print(get_subset_count(A))  # 4 - 5,13,20,37
A = [18,20,37,20,42,50,55]
print(get_subset_count(A))  # 4 - 5,13,20,37
A = [18,37,20,42,50,54]
print(get_subset_count(A))  # 5 - 18, 37, 20, 24, 30
A = [1,2,3,4,5,6,7,8,9,10]
print(get_subset_count(A))  # 4 - 1,2,3,4 or 1,2,4,8

关于运行时，我认为这是NP，因为combinations的性质。

失败点

这个方法仍然无法发现一些样本，我将用一个例子来解释：

对于A = [4,13,21,37,45,62]，存在一个下限集，即[4,8,13,37]。将集合成员分别表示为[a,b,c,d]，我们可以将A描述为

A = [a, c, c+b, d, d+b, a+b+c+d]

我建议的方法将发现该62 = 4+21+37并将其删除，然后它将不会发现该45 - 37 = 21 - 13 = 8。

改进建议

在寻找这些案例的解决方案之后，我想出了以下几点：

def get_subset_count(A):
    m = len(A)
    if m == 2:
        return 2
    elif m == 3:
        return 3 if A[0] + A[1] == A[2] else 2
    else:
        lower_bound = int(np.ceil(np.log2(m + 1)))
        for ss in range(lower_bound, m): # checking if there is a subset with size of ss
            A_temp  = A.copy()
            removed = set()
            sub_values = []
            # phase 1 - looking if a summation of components in A result in other components in A
            for kk in range(2, ss+1):
                for comb in combinations(A[:ss+1], kk):
                    if sum(comb) in A_temp:
                        A_temp.remove(sum(comb))
                        removed.add(sum(comb))
            if len(A_temp) <= ss: return ss
            # phase 2 - looking for hidden base components
            deduction = np.array(A_temp)[:, None] - np.array(A_temp)
            for comb in combinations(deduction[deduction > 0].tolist(), 2):
                if sum(comb) in A_temp: # checking if the sum is in  the array
                    A_temp2 = A_temp.copy()
                    A_temp2.remove(sum(comb))
                    comb0_logic     = [comb[0] + a in A_temp2 for a in A_temp2]
                    comb0_logic_sub = [comb[0] + a in A_temp2 for a in sub_values]
                    comb1_logic     = [comb[1] + a in A_temp2 for a in A_temp2]
                    comb1_logic_sub = [comb[1] + a in A_temp2 for a in sub_values]
                    if any(comb0_logic) and any(comb1_logic): # checking if combination is a hidden base
                        A_temp.remove(sum(comb))
                        removed.add(sum(comb))
                        A_temp.remove(sum(comb[0] + np.array(A_temp2)[comb0_logic]))
                        removed.add(sum(comb[0] + np.array(A_temp2)[comb0_logic]))
                        if comb[0] not in sub_values: sub_values.append(comb[0])  # if this sub value is not in the list, adding it
                        if comb[0] + np.array(A_temp2)[comb0_logic] != comb[1] + np.array(A_temp2)[comb1_logic]:
                            A_temp.remove(sum(comb[1] + np.array(A_temp2)[comb1_logic]))
                            removed.add(sum(comb[1] + np.array(A_temp2)[comb1_logic]))
                        if comb[1] not in sub_values: sub_values.append(comb[1])  # if this sub value is not in the list, adding it
                    elif (comb[0] in sub_values) or (comb[1] in sub_values):
                        if any(comb0_logic_sub):
                            A_temp.remove(sum(comb[0] + np.array(sub_values)[comb0_logic_sub]))
                            removed.add(sum(comb[0] + np.array(sub_values)[comb0_logic_sub]))
                            if comb[0] not in sub_values: sub_values.append(comb[0])  # if this sub value is not in the list, adding it
                        if any(comb1_logic_sub):
                            A_temp.remove(sum(comb[1] + np.array(sub_values)[comb1_logic_sub]))
                            removed.add(sum(comb[1] + np.array(sub_values)[comb1_logic_sub]))
                            if comb[1] not in sub_values: sub_values.append(comb[1])  # if this sub value is not in the list, adding it
                elif comb[0] == comb[1]:  # cases where the hidden base is not in the set but the sum of the hidden base with other parts are in the set
                    A_temp2 = A_temp.copy()
                    comb0_logic = [comb[0] + a in A_temp2 for a in A_temp2]
                    if any(comb0_logic):
                        removed_numbers = comb[0] + np.array(A_temp2)[comb0_logic]
                        for removed_number in removed_numbers:
                            A_temp.remove(removed_number)
                            removed.add(removed_number)
                    if comb[0] not in sub_values: sub_values.append(comb[0])
                elif comb[0] in sub_values and comb[1] in sub_values and sum(comb) in A_temp:  # cases where we found the base already and we need to remove a single number
                    A_temp.remove(sum(comb))
                    removed.add(sum(comb))
            # phase 3 - check if we did not forget any other number due to the order of combinations
            for kk in range(2, ss+1):
                for comb in combinations(sub_values, kk):
                    if sum(comb) in A_temp:
                        A_temp.remove(sum(comb))
            if len(A_temp) + len(sub_values) <= ss: return ss
        return len(A)