Как определить, равна ли какая-либо комбинация суммы набора значений определенному значению?

Question

У меня есть набор значений ниже. Что мне нужно выяснить, так это то, является ли любая комбинация сумм этих значений определенным значением (46 464,77 в данном случае). Каков наилучший способ выяснить это? Конечно, это займет несколько часов, чтобы сделать это вручную.

И мне нужно знать, что это за комбинация, если она вернула истину. Я мог бы установить это в Excel VBA или в приложении на C #. Что бы ни работало. Я просто понятия не имею, как туда добраться.

 125.00 
 1,000.00 
 1,039.36 
 1,171.60 
 1,200.00 
 1,320.00 
 1,680.00 
 1,757.20 
 1,768.80 
 1,970.00 
 2,231.25 
 2,300.00 
 2,369.25 
 2,589.20 
 2,720.00 
 2,887.50 
 3,000.00 
 3,085.00 
 3,142.60 
 3,174.40 
 3,742.70 
 3,847.20 
 5,609.25 
 5,881.05 
 12,240.48 
 14,112.00 
 29,318.07 
 32,551.80 

Answer 1

Как уже упоминалось в ответе Пейсли, это вариант задачи о ранце . Фактически, эта конкретная проблема называется проблемой суммы подмножеств , и, как и задача о ранце, она является NP-полной.

На связанной странице Википедии показано, как решить проблему с помощью динамического программирования, но обратите внимание, что из-за ее полноты NP решение всегда будет медленным / невозможным, если вы сделаете свой список целых чисел слишком большим.

Вот еще несколько связанных с этим вопросов:

• Подмножество сумм Задача
• Алгоритм суммы подмножеств
• Оптимизация реализации подмножества сумм

Answer 2

То, что вы описываете, является вариантом проблемы Рюкзак . Это вычислительно трудно решить эффективно, но для такого маленького набора это возможно.

Точная комбинация чисел для этого конкретного ввода:

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), поскольку сравнения с плавающей точкой являются минным полем. (Подробнее см. Что должен знать каждый компьютерщик об арифметике с плавающей точкой .)

Answer 3

Это почти точно ограниченная задача о ранце , одна из наиболее хорошо изученных вычислительных задач в истории . Локально:

• Алгоритм поиска числа из списка размером n сумма к другому числу

---

NP Complete означает, что вы должны быть готовы написать гигантский цикл , суммирующий каждую (или почти каждую) комбинацию чисел.

Я бы рекомендовал не делать это вручную. Несколько часов - это брутто недооценка. Это заняло бы всю вашу жизнь. Например, существует более 40 миллионов комбинаций из 14 чисел при выборе из пула из 28. (Это только 14).

Answer 4

Сначала прочитайте другие ответы / комментарии.Вот решение, которое можно использовать для небольшого набора данных.

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;
    }
}

Answer 5

Да, сумерки правы. ЕДИНСТВЕННАЯ комбинация, которая в сумме составляет 46134,77 это:

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

Потребовалось 2 секунды, чтобы узнать. Я использовал надстройку SumMatch Excel.