Для игры, которую я делаю, у меня есть ситуация, когда у меня есть список чисел, например [7, 4, 9, 1, 15, 2] (названный для этого A
), и другой список чисел, например [11, 18, 14 , 8, 3] (имя B
). Цель состоит в том, чтобы найти все комбинации чисел в A
, которые в сумме дают число в B
. Например:
- 1 + 2 = 3
- 1 + 7 = 8
- 2 + 9 = 11
- 4 + 7 = 11
- 1 + 2 + 4 + 7 = 14
- 1 + 2 + 15 = 18
- 2 + 7 + 9 = 18
...и так далее. (Для этого 1 + 2
совпадает с 2 + 1
.)
Для небольших списков, подобных этому, тривиально просто перебор комбинаций, но я сталкиваюсь с возможностью увидеть от тысяч до десятков тысяч этих чисел и буду использовать эту процедуру неоднократно на протяжении всего срока службы приложения. Есть ли какой-нибудь элегантный алгоритм для выполнения этого в разумные сроки со 100%-м охватом? В противном случае, есть ли какая-нибудь приличная эвристика, которую я могу найти, которая может дать мне «достаточно хороший» набор комбинаций за разумное время?
Я ищу алгоритм в псевдокоде или на любом прилично популярном и читаемом языке (обратите внимание на "и" там....;) или даже просто английское описание того, как можно реализовать такой поиск.
Отредактировано для добавления:
На данный момент предоставлено много полезной информации. Спасибо парень! Резюмируя на данный момент:
- Проблема заключается в NP-Complete, поэтому для получения 100% точности в разумные сроки не обойтись без грубой силы.
- Задачу можно рассматривать как вариант либо суммы подмножества, либо проблемы с рюкзаком. Для обоих существуют хорошо известные эвристики, которые могут быть адаптированы к этой проблеме.
Держите идеи! И еще раз спасибо!
A
. Наконец, вы проверяете для каждой комбинации, есть ли нужные числа вoccurs-in-A-list
. - person rudi-moore   schedule 05.07.2010