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

Question

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

Values =  {1, 1, 1, 2, 4, 4}

Target value = 5

Possible subsets = {1, 1, 1, 2} and {1, 4}

Теперь можно выбрать:

{1, 1, 1, 2} (= worth 5)

или

{1, 4} {1, 4} (= worth 10)

Так что в этом примере я хотел быалгоритм возврата 10, а не 5.

Мне удалось решить часть «поиск возможных подмножеств», но я не могу найти наиболее ценную комбинацию найденных подмножеств.Может кто-нибудь мне помочь?(

Answer 1

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

{1,4} равно {1,4}

{1,4} равно{4,1}?

{1,4} отличается от {1,1,1,2}

Итак, вам необходимо убедиться, что ваша программа может работать правильносравнение.Для этого вам потребуется сгенерировать «подпись» комбинации, то есть значение (например, строку), поэтому, когда вас интересует, равны ли две группы, вы сравниваете их сигнатуру.Вам понадобится структура данных (Карта), состоящая из единственного числа и номера, в которой будут храниться все обнаруженные подписи и номер их появления.Всякий раз, когда вы получаете комбинацию, вам нужно будет выяснить, содержит ли карта данную подпись.Если так, увеличивайте вхождение.Если нет, добавьте подпись на карту со значением 1. После того, как вы нашли все комбинации, найдите запись на карте с наибольшим значением, и это будет решением.

Теперь давайте вернемся квопрос о том, равняется ли

{1,4} {4,1}?

Если они равны, то вам нужно будет отсортировать элементы комбинации, прежде чем создавать ее сигнатуру,Если они не равны (это означает, что мы имеем дело с вариациями), вам не нужно сортировать элементы, просто сгенерируйте подпись в их необработанном виде.