Как найти, какие числа в наборе составляют в целом другое данное число?

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

Тем не менее, существуют ранцевые решатели на основе генетических алгоритмов.

Это версия задачи о ранце . Это полная NP, поэтому вы не получите хорошего общего ответа. Насколько велики ваши наборы транзакций? Это 5, как вы показали, или это больше похоже на 500?

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

Даны целые числа [a_1, ..., a_n] и число T,

Определите массив S [i, k], чтобы обозначить, существует ли подмножество элементы между a_1, ... a_i, которые в сумме дают k. (Это двоичная матрица.)

Затем мы можем определить рекурсивное отношение следующим образом:

S [i, k] = S [i-1, k] или S [i-1, k-a_j]

На словах это означает, что мы либо используем элемент a_i, либо нет. Ответ будет расположен в S [n, T].

Какова рабочая нагрузка для построения матрицы S? Ну, у S есть n * T элементов. Чтобы вычислить каждый элемент, мы должны выполнить O (1) работу. Итак, полный ход время O (n * T).

Теперь мне кажется, что я доказал, что P = NP, так как это кажется алгоритмом полиномиального времени. Однако помните что мы измеряем размер входных данных в двоичном формате, поэтому T = 2 ^ p для некоторых стр.

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

Также есть некоторые эвристики для решения этой проблемы, но я не эксперт в этой области.

OK. Многие люди назвали проблему и упомянули, насколько она сложна. И в целом они правильные. Однако у вас есть очень конкретный случай, который вам нужно решить. Первый вопрос, который следует задать, - считаете ли вы, что ваши 100 транзакций близки к правильным. У вас есть некоторая сумма («ваша» сумма). У них есть какая-то сумма. («реальный» итог). Поэтому некоторые из ваших транзакций являются фиктивными. Если вы подозреваете, что там всего несколько фиктивных транзакций, то это не так уж и плохо. Например, пусть ' s рассмотрим случай, когда существует только одна фиктивная транзакция. В этом случае нам нужно будет проверить только 100 разных чисел. Если есть 2 фиктивных транзакции, то вы смотрите на 100 * 99 проверок, и все станет сумасшедшим при 4 фиктивных транзакциях с почти 100000000 шагов. хотя, если все, что вы делаете, это добавляете несколько int, это не так уж и страшно.

Другой возможный ярлык - изучить природу ваших данных (кстати, можно ли опубликовать 100 «чисел» и ожидаемую сумму?). Насколько ваша сумма больше реальной? Существуют ли какие-либо значения настолько большие, что при их устранении ваша сумма внезапно окажется ниже реальной суммы? Если это так, то вы знаете, что эти значения не могут быть фиктивными. Например, в вашем примере 7 обязательно.

d нужно только проверить 100 разных чисел. Если есть 2 фиктивных транзакции, то вы смотрите на 100 * 99 проверок, и все станет сумасшедшим при 4 фиктивных транзакциях с почти 100000000 шагов. хотя, если все, что вы делаете, это добавляете несколько int, это не так уж и страшно.

Другой возможный способ сокращения - это изучить природу ваших данных (кстати, можно ли опубликовать 100 «чисел» и ожидаемую сумму?). Насколько ваша сумма больше реальной? Существуют ли какие-либо значения настолько большие, что при их устранении ваша сумма внезапно окажется ниже реальной суммы? Если это так, то вы знаете, что эти значения не могут быть фиктивными. Например, в вашем примере 7 обязательно.

d нужно только проверить 100 разных чисел. Если есть 2 фиктивных транзакции, то вы смотрите на 100 * 99 проверок, и все станет сумасшедшим при 4 фиктивных транзакциях с почти 100000000 шагов. хотя, если все, что вы делаете, это добавляете несколько int, это не так уж и страшно.

Другой возможный способ сокращения - это изучить природу ваших данных (кстати, можно ли опубликовать 100 «чисел» и ожидаемую сумму?). Насколько ваша сумма больше реальной? Существуют ли какие-либо значения настолько большие, что при их устранении ваша сумма внезапно окажется ниже реальной суммы? Если это так, то вы знаете, что эти значения не могут быть фиктивными. Например, в вашем примере 7 обязательно.

000 шагов. хотя, если все, что вы делаете, это добавляете несколько int, это не так уж и страшно.

Другой возможный ярлык - изучить природу ваших данных (кстати, можно ли опубликовать 100 «чисел» и ожидаемую сумму?). Насколько ваша сумма больше реальной? Существуют ли какие-либо значения настолько большие, что при их устранении ваша сумма внезапно окажется ниже реальной суммы? Если это так, то вы знаете, что эти значения не могут быть фиктивными. Например, в вашем примере 7 обязательно.

000 шагов. хотя, если все, что вы делаете, это добавляете несколько int, это не так уж и страшно.

Другой возможный ярлык - изучить природу ваших данных (кстати, можно ли опубликовать 100 «чисел» и ожидаемую сумму?). Насколько ваша сумма больше реальной? Существуют ли какие-либо значения настолько большие, что при их устранении ваша сумма внезапно окажется ниже реальной суммы? Если это так, то вы знаете, что эти значения не могут быть фиктивными. Например, в вашем примере 7 обязательно.

Насколько ваша сумма больше реальной? Существуют ли какие-либо значения настолько большие, что при их устранении ваша сумма внезапно окажется ниже реальной суммы? Если это так, то вы знаете, что эти значения не могут быть фиктивными. Например, в вашем примере 7 обязательно.

Насколько ваша сумма больше реальной? Существуют ли какие-либо значения настолько большие, что при их устранении ваша сумма внезапно окажется ниже реальной суммы? Если это так, то вы знаете, что эти значения не могут быть фиктивными. Например, в вашем примере 7 обязательно.