Алгоритм выбора определенного количества элементов из набора для достижения некоторого значения

Question

Данный набор элементов n [1], n [2], n [3], .... n [x] и число V. (Элементы имеют свои собственные значения)

Я хотел бы найти все комбинации элементов, которые удовлетворяют следующим условиям:

1) Каждая комбинация содержит определенное количество элементов (например, ровно 5 элементов)

Комбинация № 1: n [1], n [2], n [21], n [22], n [24]

Комбинация № 2: n [1], n [2], n [12], n [15], n [33]

......

2) Сумма значений элементов в комбинации должна быть меньше заданного числа V (например, V = 100)

Комбинация № 1: n [1] + n [2] + n [21] + n [22] + n [24] <100 </p>

Комбинация № 2: n [1] + n [2] + n [12] + n [15] + n [33] <100 </p>

......

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

Спасибо

Answer 1

Поскольку вам, вероятно, все равно придется использовать грубую силу, вы можете решить свою проблему следующим образом:

Прежде всего, отсортируйте входной набор S.

Затем удалите все элементыот S, которые больше V - 4*|min| (где |min| - абсолютное значение наименьшего элемента), потому что они все равно не появятся ни в одном из ваших решений.В зависимости от вашей конкретной задачи, эта оптимизация может быть улучшена в дальнейшем.

Теперь вы генерируете все суммы длины C элементов в S, начиная с наименьшего возможного числа (помните, что S сортируется).

Если результат меньше V, добавьте его в набор решений и увеличьте последнее слагаемое.

В противном случае установите ранее увеличенное слагаемое и все слагаемые после него на минимально возможные значения и увеличьтеСлагаемое перед этим.

Вы можете остановиться, если все слагаемые достигли максимально возможных значений.Возможно, вам удастся остановиться задолго до этого, что оставлено читателю в качестве упражнения из-за моего неаккуратного английского.

Answer 2

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

http://en.wikipedia.org/wiki/Knapsack_problem

Тем не менее, говорят, что проблема с рюкзаком имеет сложность NP-завершения, которую нужно решить точно ... Это плохие новости. Поэтому люди предлагают использовать алгоритм обратного отслеживания.

Я уверен, что в Google вы найдете много кодов о возврате для проблемы с ранцем.

Надеюсь, это поможет