Очень большое количество комбинаций никогда не дает результатов - PullRequest
Новая
       32

Очень большое количество комбинаций никогда не дает результатов

0 голосов
/ 07 января 2019

Я использую win 10 и Python 3.6.3. У меня есть список словарей - в моем списке около 200 словарей. Это выглядит так: 

my_list = [{"name": "object_1", "price": 9, "reward": 5}, {"name": "object_2", "price": 9.3, "reward": 4.9},....]

Я использую этот код для получения всех возможных комбинаций из 10 объектов: 

total_combinations = itertools.combinations(my_list, 10)

Затем я буду использовать некоторые критерии для достижения наиболее эффективной комбинации - например, максимизировать общее вознаграждение при общей стоимости 90.

Проблема заключается в том, что существует огромное количество комбинаций, в частности 22,451,004,309,013,280 комбинаций. Это очень большое число, и до сих пор, когда я пытался применить свои критерии, Python либо падал (у меня 8 ГБ ОЗУ), либо он никогда не возвращал никаких результатов. Например, приведенный ниже код никогда не возвращает никаких результатов: 

total_combinations = itertools.combinations(my_list, 10)
for i in total_combinations:
    total_cost = 0
    total_reward = 0
    for j in i:
        total_cost += j["price"]
        total_reward += j["reward"]
    if total_cost > 80 and total_cost < 85:
        print(total_cost, total_reward, i)

Если, однако, в my_list я включаю только 20 словарей (то есть "всего" 184 756 различных комбинаций), Python требуется около 30 секунд для обработки моего кода и отображения результатов.

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

Спасибо.

...