algorithm - Min-Coin Change 变化

Question

Min-Coin Change 问题已得到充分研究(可以在此处找到解释:http://www.algorithmist.com/index.php/Min-Coin_Change)，但我有兴趣解决它的变体:

For a set of values V, determine a minimal set of coins C such that each of the values in V can be obtained as a sum of coins in C, where each coin in the set may only be used at most once. By minimal we mean the least number of coins.

例如，如果 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。我正在寻找可以向我展示更好的解决方案或为我指明相关方向的人问题。

编辑:请注意，可能有多个最小集合，我只想找到其中一个。

Answer 1

只是一个非常部分的解决方案/评论:

如果你的集合 V 的大小为 N，那么你在 C 中至少需要 ceil[log_2(N)] 个元素。事实上，你可以用一组 m 个元素生成的值的数量最多为 2^m 等等你必须有 2^|C| >= N.

如果 V 中至少但不是所有数字中设置为 1 的总位数(在数字的二进制表示中)等于 n，则 C 中最多需要 n 个元素。此外，你通过让 C = {2^{x_1}*r, .., 2^{x_n}*r} 得到这个大小的集合 C 其中 x_i 是至少在一个但不是所有元素中设置为 1 的位V，r由V的所有元素中设置为1的位组成。

在您的情况下，您可以观察到两个边界匹配，因此上面第二段构造的集合 C(实际上等于您建议的集合)是您问题的解决方案。

编辑

基于以上，下面的构造呢:

设n为V的二进制表示最大元素的位数。

令 S = {1, .., n}。令 T 为在 V 的所有元素中设置为零的位集。令 S_0 为在 V 的所有元素中设置为 1 的位集。设 x_1 为 S\setminus (T\cup 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_0,x_1, .., x_r 获得 Cx_i = sum_{j\cup S_i} 2^j

我相当确信这会产生最佳集合 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}。