Оптимальный выбор группы из словаря Python

Question

Итак, у меня есть словарь с ключом: значение (кортеж). Что-то вроде этого. {"name" :( 4,5), ....} где (4,5) представляет две категории (cat1, cat2). Учитывая максимальное число для второй категории, я хотел бы найти оптимальную комбинацию словарных статей, такую, чтобы 1-я категория была максимизирована или минимизирована.

Например, если maxCat2 = 15, я хочу найти некоторую комбинацию записей из словаря, чтобы при добавлении значений cat2 из каждой записи мне было меньше 15. Таких условий может быть много. Из этих возможностей я хотел бы выбрать тот, который, когда я складываю значения для cat1 для каждой записи, больше, чем любая другая возможность.

Я подумал о написании алгоритма для получения всех перестановок записей в словаре, а затем посмотреть, соответствует ли каждая из них критериям maxCat2, а затем посмотреть, какая из них дает мне наибольшее общее значение cat1. Если у меня 20 записей, значит, я бы проверил 20! комбинаций, что очень большое количество. Что я могу сделать, чтобы избежать этого? Благодарю.

Answer 1

Как указал Йохен Ритцель , это можно рассматривать как пример проблемы с рюкзаком .

Как правило, у вас есть набор объектов, которые имеют как «вес» («вторая категория», в вашем примере), так и «значение» (или «стоимость», если это проблема минимизации).

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

Хотя проблема в общем неразрешима, если ограничение на максимальное значение для суммы весов является фиксированным, существует полиномиальное временное решение, использующее динамическое программирование или памятка .

Очень широко идея состоит в том, чтобы определить набор значений, где

C _ij обозначает максимальную сумму («значений»), достижимую с учетом только первых i объектов, где общий вес (выбранного подмножества) не может превышать j .

Здесь есть два возможных варианта вычисления C _ij .

• любой элемент i включается в подмножество, а затем

  C _ij = значение _i + C _{i-1, вес j я}

• или элемент i не входит в подмножество выбранных объектов, поэтому

  C _ij = C _{i-1, j}

Необходимо выбрать максимум из двух.

Если n - это количество элементов, а w - это максимальный общий вес, то ответ заканчивается на C _nw .