Сложные перестановки без повторения

Question

Я пытаюсь создать инструмент для игры под названием Monster Hunter (для личного использования). Я работал с перестановками раньше, но ничего сложного, поэтому я полностью застрял.

В игре вы носите 5 единиц брони. Каждая часть имеет очки навыков для одного из множества различных навыков. Если у вас есть 10+ очков навыка в определенном навыке после расчета всего набора, вы зарабатываете этот навык.

Пример:

Foo Head: Attack +2, Guard + 2
Foo Chest: Defense + 5    
Foo Body: Guard + 2, Attack + 5, Defense +2
Foo Arm: Attack + 3, Speed + 4
Foo Legs: Attack + 5, Guard + 6, Defense + 3

The above set would result in 10+ in Attack, Defense, and Guard (not speed).

Я хотел бы выяснить, как найти все комбинации частей брони с 2-3 указанными пользователем навыками. Таким образом, если вы выбрали "Атака" и "Скорость", это дало бы вам все возможные комбинации из 5 частей брони, которые приведут к +10 как в "Атаке", так и в "Скорости". Есть около 60 различных предметов для каждой из 5 категорий.

Я знаю, что могу использовать LINQ для фильтрации каждой из 5 категорий частей брони, так что я получаю только список всех предметов, которые включают одно из 2 указанных умений, но я теряюсь, как делать перестановки, так как я жонглирование 2-3 пользовательских навыков...

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

Answer 1

1) Я бы попытался найти только 1 навык, а затем отфильтровать этот набор предметов для второго / третьего

2) чтобы не тратить слишком много времени / памяти / рекурсии: я бы отсортировал 5 * 60 предметов, основываясь на этом единственном умении. Затем я бы создавал комбинации, ища те, которые в сумме превышают 10, начиная с верхних умений и заканчивая либо при достижении 10, либо когда оно не будет достигнуто.
Функция, которая строит все комбинации, будет выглядеть так: 1: если у нас общий навык предмета>10: все комбинации с другими предметами в порядке. стоп. 2: если текущий навык предмета равен <10, ищите в массиве следующий самый большой предмет для не изношенного предмета.
если в массиве мы достигли 0 ИЛИ мы достигли значения, такого, что (текущий счет + значение * количество оставшихся частей типа) <10, то время останавливаться:-)
В противном случае добавьте счетчик умений, отметьте используемый тип брони, а затем вызовите свою функцию для всех предметов, которые могут совпадать.

Возможно, я не достаточно точен, но вы видите идею: используйте условие для вызова, чтобы избежать взрыва рекурсивности. Потому что 60*60*60*60*60 - это много. и (быстрая) сортировка 5*60=300 предметов - это ничто.

Для хранения ваших комбинаций вы можете добавить случай "все идет", чтобы избежать хранения / вычисления слишком большого количества комбинаций для ничего. (например: если у вас есть Carmak's Magical Hat, у вас +100 в коде, и вы можете одеваться так, как хотите, ошибки будут окрашиваться!:-))