微硬币变化变化

Question

民币变化问题得到了很好的研究(在这里可以找到一个解释：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。

到目前为止，我想不出比蛮力强制子集更好的工作方法了，这显然不适用于大型V。我正在寻找一个人，要么给我一个更好的解决方案，要么给我指明相关问题的方向。

编辑:请注意，可能有多个最小集，我感兴趣的只是其中的一个。

Answer 1

只是一个非常片面的解决方案/评论：

如果集合V的大小为N，则至少需要C中的ceillog_2( N )元素。实际上，使用一组m元素可以生成的值的数目最多为2^m，因此必须有2^x-C\ >= N。

如果总位数(在数字的二进制表示中)至少设置为1，但并非所有V数都等于n，那么在C中最多需要n个元素，而且，通过允许C= {2^{x_1}*r，.，2^{x_n}*r}，使C={2^{x_n}*r}得到这样大小的集合C，其中x_i是设置为至少一个而不是V的所有元素中的一个的位，而r是由V的所有元素中的一个所设置的。

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

编辑

基于以上所述，以下结构如何：

设n是V的二进制表示极大元中的位数。

设S= {1，..，n}。设T是在V的所有元素中设置为零的位集。让S_0是在V的所有元素中设置为1的位集。设x_1是S\ set减号的第一个元素(T \杯S_0)。让S_1由V中所有元素中与x_1值相同的所有位组成。让x_2是S\set减号的第一个元素(T \ S_0 \S_0 S_1)。让S_2在V的所有元素中由所有与x_2值相同的位组成。。。以此类推，直到S= (T \杯S_0 \杯S_1 \ S_r)。

然后，考虑由x_0，x_1，.，x_r定义的x_i = sum_{j \杯S_i} 2^j的数，得到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}。