Добавление ограничений категорий в алгоритм рюкзака

Я пытаюсь реализовать алгоритм рюкзака, чтобы играть в фэнтези-баскетбол. Я написал традиционный решатель рюкзака 0/1, который берет пары значений и весов (цен) для каждого игрока и выводит наиболее ценную комбинацию игроков, чья совокупная зарплата меньше, чем потолок зарплат.

Тем не менее, фэнтезийное соревнование требует, чтобы вы составляли свой состав из 8 игроков на основе позиций, которые играют игроки, т. е. ваш состав должен состоять из 1 разыгрывающего, 1 атакующего защитника, 1 легкого нападающего, 1 сильного форварда, атакующий защитник или разыгрывающий, 1 легкий нападающий или мощный форвард и 1 игрок любой позиции.

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


algorithm knapsack-problem dynamic-programming
person sfenske    schedule 21.12.2015    source источник

Ответы (2)


arrow_upward
0
arrow_downward

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

person Sorin    schedule 21.12.2015

arrow_upward
0
arrow_downward

Как сказал Сорин, вам нужно другое состояние в вашем DP, чтобы отслеживать заполненные позиции.

Используйте битовую маску для третьего состояния вашего DP, где бит ith указывает, занята ли уже роль ith. Например, 255 = (11111111), что означает, что все возможные роли заняты.

Это жизнеспособно, потому что количество ролей всего восемь. Кроме того, вам нужен только один игрок на роль. Поэтому для третьего состояния требуется относительно небольшой массив (2^8 = 256). Теоретически можно использовать большие базы вместо бинарной. Обычно для третьего состояния требуется массив размером b^r, где b = количество игроков на роль + 1 и r = количество ролей, но использование памяти может быть огромным.

person Emerson Leonardo Lucena    schedule 22.12.2015