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 . 我正在寻找有人向我展示更好的解决方案或指向我相关问题的方向 .
编辑：请注意，可能有多个最小集合，我有兴趣找到其中一个 .
1 回答
只是非常局部的解决方案/评论：
如果您的集合V的大小为N，那么在C中至少需要ceil [log_2（N）]个元素 . 实际上，使用一组m个元素生成的值的数量最多为2 ^ m，因此您必须具有2 ^ | C | > = N.
如果在至少但不是所有V的数量中设置为1的总位数（在数字的二进制表示中）等于n，则在C中最多需要n个元素 . 此外，您得到一组通过使C = {2 ^ * r，..，2 ^ * r}来确定此大小的C，其中x_i是在V的至少一个但不是所有元素中设置为1的位，并且r由在V的所有元素中设置为1的位组成 .
在您的情况下，您可以观察到两个绑定匹配，因此上面第二段构造的集合C（实际上等于您建议的那个）是您的问题的解决方案 .
EDIT
基于以上所述，以下结构如何：
令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} .