Min-Coin Change 问题已得到充分研究（可以在此处找到解释：http ://www.algorithmist.com/index.php/Min-Coin_Change ），但我有兴趣解决它的变体：
对于一组值 V，确定最小的硬币集 C，使得 V 中的每个值都可以作为 C 中的硬币的总和获得，其中该组中的每个硬币最多只能使用一次。最小是指最少的硬币数量。
例如，如果 V = {3, 8, 9, 10, 11} 那么很容易看出 C = {1, 2, 8} 因为 1 + 2 = 3, 8 = 8, 9 = 1 + 8, 10 = 2 + 8 和 11 = 1 + 2 + 8。没有更小的集合 C' 也涵盖所有这些数量。
到目前为止，我想不出比暴力破解子集更好的工作方法，这显然不适用于大 V。我正在寻找有人向我展示更好的解决方案或为我指出相关问题的方向。
编辑：请注意，可能有多个最小集，我有兴趣只找到其中一个。
只是一个非常部分的解决方案/评论：
如果您的集合 V 的大小为 N，那么您至少需要 C 中的 ceil[log_2(N)] 个元素。确实，您可以使用一组 m 个元素生成的值的数量最多为 2^m，因此您必须具有2^|C| >= N。
如果至少在 V 的所有数字中设置为一个但不是所有数字的总位数（以数字的二进制表示）等于 n，那么您最多需要 C 中的 n 个元素。此外，您会得到一个集合通过让 C = {2^{x_1}*r, .., 2^{x_n}*r} 得到这个大小的 C，其中 x_i 是设置为 V 的至少一个但不是所有元素中的一个的位，并且r 由 V 的所有元素中设置为 1 的位组成。
在您的情况下，您可以观察到两个绑定匹配，因此上面第二段构造的集合 C（实际上等于您建议的集合）是您问题的解决方案。
编辑
基于以上内容，以下构造如何：
令 n 为 V 的二进制表示最大元素中的位数。
令 S = {1, .., n}。令 T 为在 V 的所有元素中设置为零的位集合。令 S_0 为在 V 的所有元素中设置为 1 的位集合。令 x_1 为 S \setminus (T \杯 S_0)。令 S_1 由 V 的所有元素中与 x_1 取相同值的所有位组成。令 x_2 为 S \setminus (T \cup S_0 \cup S_1) 的第一个元素。让 S_2 由 V 的所有元素中与 x_2 取相同值的所有位组成。让 x_3 .. .. 依此类推，直到 S = (T \cup S_0 \cup S_1 \cup S_r)。
然后通过考虑由 x_i = sum_{j \cup S_i} 2^j 定义的数字 x_0,x_1, .., x_r 获得 C
我相当确信这会产生一个最优集合 C（尽管我还没有证据）。
例如，在您的示例中，您将使用二进制表示 3 = 0011 8 = 1000 9 = 1001 10 = 1010 11 = 1011
所以T_0 = {3}，S_0 = {}，S_1 = {1}，S_2 = {2}，S_3 = {4}。