如何确定一组值之和的任何组合是否等于某个值

本文关键字：任何 和的 组合 是否 于某个 一组 何确定 | 更新日期: 2023-09-27 18:22:08

下面有一组值。我需要弄清楚的是，这些值的任何组合是否等于某个值（在这种情况下为46134.77）。解决这个问题的最佳方法是什么？当然，手动操作需要几个小时。

如果它是真的，我需要知道组合是什么。我可以在Excel VBA或C#应用程序中进行设置。什么都行。我只是不知道怎么去那里。

1251000.001039.361171.601200.001320.001680.001757.201768.801970.002231.252300.002369.252589.202720.002887.503000.003085.003142.603174.403742.703847.205609.255881.0512240.4814112.0029318.0732551.80

如何确定一组值之和的任何组合是否等于某个值

正如paislee的回答中已经提到的，这是背包问题的一个变体。事实上，这个特定的问题被称为子集和问题，就像背包问题一样，它是NP完全的。

链接的维基百科页面显示了如何使用动态编程来解决问题，但请注意，由于其NP完全性，如果你的整数列表太大，解决问题总是很慢/不可能。

以下是一些更相关的SO问题：

  • 子集和问题
  • 子集求和算法
  • 优化子集和实现

这几乎是一个有界背包问题，是历史上研究最深入的计算问题之一。本地：

  • 从大小为n的列表中找出哪些数字与另一个数字求和的算法

NP完全意味着您应该准备好编写一个巨大循环，将每个（或几乎每个）数字组合相加。

我建议不要用手做这件事。几个小时被严重低估了这会花你一辈子的时间例如，当从28个数字中进行选择时，有超过4000万个14个数字的组合。（这只是14岁）。

您所描述的是背包问题的一个变体。它在计算上很难有效求解，但对于这么小的集合来说，它是可行的。

该特定输入的确切数字组合为：

29,318.07 + 5,881.05 + 3,174.40 + 3,085.00 + 2,231.25 + 1,320.00 + 1,000.00 + 125.00

我使用以下Perl脚本来确定这个解决方案：

sub knapsack {
    my ($target, $path, @vals) = @_;
    if ($target == 0) {
        print "Got it: @$path'n";
        exit;
    }
    while (my $val = pop @vals) {
        next if $val > $target;
        knapsack($target - $val, [@$path, $val], @vals);
    }
}
knapsack(46134_77, [], (
    125_00,  1000_00, 1039_36, 1171_60, 1200_00, 1320_00, 1680_00, 1757_20,
    1768_80, 1970_00, 2231_25, 2300_00, 2369_25, 2589_20, 2720_00, 2887_50,
    3000_00, 3085_00, 3142_60, 3174_40, 3742_70, 3847_20, 5609_25, 5881_05,
    12240_48, 14112_00, 29318_07, 32551_80,
));

请注意，我已经将您的十进制值转换为整数（将它们全部乘以100），因为浮点比较是一个雷区。（请参阅每个计算机科学家都应该知道的浮点运算了解详细信息。）

请先阅读其他答案/评论。以下是一个可用于小数据集的解决方案。

double[] nums = new double[] { 10,20,30,40,50,60,70,80,90,100,150,200,250,300,400,500};
Parallel.ForEach(GetIndexes(nums.Length), list =>
{
    if (list.Select(n => nums[n]).Sum()==350)
    {
        Console.WriteLine(list.Aggregate("", (s, n) => s += nums[n] + " "));
    }
});
IEnumerable<IEnumerable<int>> GetIndexes(int count)
{
    for (ulong l = 0; l < Math.Pow(2, count); l++)
    {
        List<int> list = new List<int>();
        BitArray bits = new BitArray(BitConverter.GetBytes(l));
        for (int i = 0; i < sizeof(ulong)*8; i++)
        {
            if (bits.Get(i)) list.Add(i);
        }
        yield return list;
    }
}
是的，duskwuff是对的。唯一的组合，总计46134.77这是吗

1251000.001320.002231.253085.003174.405881.0529318.07

花了2秒钟才发现。我使用了SumMatch Excel加载项。

相关文章：