Задача алгоритма комбинаций

Question

Я пытаюсь решить эту проблему уже более месяца. У меня есть список номеров и этих переменных:

list_num = [1, 1, 2, 3, 5, 6, 1, 1, 3, 4, 4] 

#x is number of numbers in combination eg. if x = 5 combiantions will look like this [n,n,n,n,n], where n is possible member of list _num 
x = 5 
#y is a sum of numbers inside combination 
y = 10 

У меня есть необходимость создания всех возможных комбинаций этих цифр в том, что x это количество чисел в комбинации и y является сумма чисел в комбинации, также необходимо учитывать количество повторяющихся внутри list_num.

Я могу сделать это, создав всю возможную комбинацию и исключив комбинации, которые не определены моими правилами, но этот метод беспорядочен, и я не могу использовать его с большим количеством данных. В шахтной оригинальной программе list_num может иметь сотни чисел и переменных x и y могут иметь большие значения.

Пара комбинаций для этого примера:

comb1 = [1,1,2,3,3], x = 5, y = 10 
comb2 = [1,1,1,2,5], x = 5, y = 10 
comb3 = [1,1,1,1,6], x = 5, y = 10 

... 

Я был бы признателен за какие-то новые идеи, я их не осталось :)

Answer 1

Это является NP-полной проблемой, пожалуйста, найдите оптимальное решение для этого по адресу:

http://en.wikipedia.org/wiki/Subset_sum_problem

Answer 2

Для базы 10 выходных номеров вы можете просто посчитать переменную вверх , сделать сумму и выхода знаковой комбинацию, если сумма знака, например, 10.

Код:

def SignSum(X): 
    Sum = 0 

    String = str(X) 

    for Sign in String: 
     Sum += int(Sign) 

    return Sum 

Counter = 0 


while Counter < 10000: 
    if SignSum(Counter) == 10: 
     print Counter 

    Counter += 1 

это, конечно, работает и с другими базами с функцией модифицирована SignSum()

Answer 3

Вот идея:

1) Сортировка список

2) Используйте массив А из й элементов - это будут индексами

3) инициализировать быть [0,1,2, ..., х-1]

4) Теперь начинайте увеличивать индексы лексикографическими, например, сначала увеличьте последнее, пока сумма не получит> y.Затем увеличьте Предпоследняя и сделать последний будет 1 + второй к последнему

и так далее

Fisrt несколько итераций:

отсортированный массив: [1, 1, 1, 1, 2, 3, 3, 4, 4, 5, 6]

А: [0,1,2,3,4]

А: [0,1,2,3,5]

A: [0,1,2,3,6]

А: [0,1,2,3,7]

А: [0,1,2,3,8]

А: [0,1,2,3,9]

А: [0,1,2,3,10] - раствор

А: [0,1,2,4,5]

А: [0,1,2,4, 6]

A: [0,1,2,4,7]

А: [0,1,2,4,8]

А: [0,1,2,4,9] - раствор

А: [0,1,2,4,10] -> у

А: [0,1,2,5,6]

А: [0,1,2,5,7] - раствор

т.д.