找到使给定数组所需的最小硬币数量

Question

问题

给定一个整数数组A，其中1<=A[i]<=1000000。

找到一个最小的正整数多重集合S(就像硬币一样)，使得对于每个A[i]，存在S的一个子集，其总和等于A[i]。

示例1

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

输出：2，其中一个最小多重集合是{1,27}。

示例2

输入：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)。使用Gauss消元法在O(5^3)内解五个线性方程，然后使用背包算法另外检查A[5]。如果没有解，则答案为6，否则S的大小最多为5。再次重复上述过程，假设S的大小为4，直到找到正确的解决方案。

这些（难以用蛮力方法编写的）问题是否有一些正式术语？

- Voyager

---

评论不适合进行长时间的讨论；此对话已被移至聊天室。 - Ryan M

Answer 1

在下面的答案中，我将考虑数组A，其中所有的值都是严格正数，并且数组中的值是唯一的。首先，我想从相对明显的事实开始。

1. 如果数组A有2个数字，最小的数字集合就是两个（即集合A本身）
2. 如果数组A有3个数字，最小的数字集合将为2，当且仅当最小数字的和等于第三个数字时，否则将为3（即集合A本身）

在注意到这一点之后，我想从相反的方向来看问题，这将为我们解决问题提供洞察力。给定一个包含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），我们可以推导出最小集合数的下界：

下界 = 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问题。

失败点

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

对于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)

- Tomer Geva

---

在测试用例A=[1,2,3,4,5,6,7,8,9,10]中，WA输出为10，期望值应该是<=4。 - Voyager

@Voyager 已经修复了，现在应该可以处理这种情况（以及我发现的另一种不起作用的情况）。 - Tomer Geva

你能澄清一下这个建议解决方案中的缺陷吗？由于您似乎正在迭代所有可能组合的集合，因此不清楚为什么会有任何情况无法正常工作。然而，在测试用例 [4, 13, 21, 37, 45, 62] 上出现了 WA，输出为 5，预期为 4（例如使用 [4、8、13、37]）。 - kcsquared

@kcsquared，我已经添加了解释，非常感谢您的反馈。 - Tomer Geva