Алгоритм определения того, какие числа из списка размера n суммируются с другим числом
-
01-07-2019 - |
Вопрос
У меня есть десятичное число (назовем его цель) и массив других десятичных чисел (назовем массив элементы) и мне нужно найти все комбинации чисел из элементы какая сумма к цели.
Я отдаю предпочтение решению на C# (.Net 2.0), но пусть лучший алгоритм победит в любом случае.
Сигнатура вашего метода может выглядеть примерно так:
public decimal[][] Solve(decimal goal, decimal[] elements)
Решение
Интересные ответы.Спасибо за ссылки на Википедию - хотя они и интересны, но на самом деле они не решают проблему, как указано, поскольку я искал точные совпадения - это скорее проблема бухгалтерского учета/балансировки книг, чем традиционная проблема с упаковкой мусора/рюкзаком.
Я с интересом следил за развитием переполнения стека и задавался вопросом, насколько это будет полезно.Эта проблема возникла на работе, и я задался вопросом, может ли переполнение стека дать готовый ответ (или лучший ответ) быстрее, чем я мог бы написать его сам.Спасибо также за комментарии, предлагающие пометить это как домашнее задание — я думаю, это достаточно точно в свете вышесказанного.
Для тех, кому интересно, вот мое решение, которое использует рекурсию (естественно). Я также передумал о сигнатуре метода и выбрал List> вместо decimal[][] в качестве типа возвращаемого значения:
public class Solver {
private List<List<decimal>> mResults;
public List<List<decimal>> Solve(decimal goal, decimal[] elements) {
mResults = new List<List<decimal>>();
RecursiveSolve(goal, 0.0m,
new List<decimal>(), new List<decimal>(elements), 0);
return mResults;
}
private void RecursiveSolve(decimal goal, decimal currentSum,
List<decimal> included, List<decimal> notIncluded, int startIndex) {
for (int index = startIndex; index < notIncluded.Count; index++) {
decimal nextValue = notIncluded[index];
if (currentSum + nextValue == goal) {
List<decimal> newResult = new List<decimal>(included);
newResult.Add(nextValue);
mResults.Add(newResult);
}
else if (currentSum + nextValue < goal) {
List<decimal> nextIncluded = new List<decimal>(included);
nextIncluded.Add(nextValue);
List<decimal> nextNotIncluded = new List<decimal>(notIncluded);
nextNotIncluded.Remove(nextValue);
RecursiveSolve(goal, currentSum + nextValue,
nextIncluded, nextNotIncluded, startIndex++);
}
}
}
}
Если вы хотите, чтобы приложение проверило эту работу, попробуйте этот код консольного приложения:
class Program {
static void Main(string[] args) {
string input;
decimal goal;
decimal element;
do {
Console.WriteLine("Please enter the goal:");
input = Console.ReadLine();
}
while (!decimal.TryParse(input, out goal));
Console.WriteLine("Please enter the elements (separated by spaces)");
input = Console.ReadLine();
string[] elementsText = input.Split(' ');
List<decimal> elementsList = new List<decimal>();
foreach (string elementText in elementsText) {
if (decimal.TryParse(elementText, out element)) {
elementsList.Add(element);
}
}
Solver solver = new Solver();
List<List<decimal>> results = solver.Solve(goal, elementsList.ToArray());
foreach(List<decimal> result in results) {
foreach (decimal value in result) {
Console.Write("{0}\t", value);
}
Console.WriteLine();
}
Console.ReadLine();
}
}
Я надеюсь, что это поможет кому-то быстрее получить ответ (будь то домашнее задание или что-то еще).
Ваше здоровье...
Другие советы
Проблема суммы подмножества и несколько более общая проблема о рюкзаке решаются с помощью динамического программирования:Перебор всех комбинаций методом перебора не требуется.Обратитесь к Википедии или к справочнику по вашим любимым алгоритмам.
Хотя задачи NP-полны, они очень «легки» NP-полны.Алгоритмическая сложность по количеству элементов невелика.
Я думаю, у тебя есть проблема с упаковкой мусорного бака на ваших руках (что NP-сложно), поэтому я думаю, что единственное решение — попробовать все возможные комбинации, пока не найдете ту, которая работает.
Редактировать:Как указано в комментарии, вы не будете всегда надо попробовать каждый комбинация для каждый набор цифр, с которыми вы столкнетесь.Однако любой метод, который вы придумаете, содержит наборы чисел для наихудшего сценария, в которых вы воля надо попробовать каждый комбинация — или, по крайней мере, подмножество комбинаций, которое растет экспоненциально с размером набора.
В противном случае это не было бы NP-сложно.
Вы описали проблема с рюкзаком, единственное верное решение – грубая сила.Есть некоторые аппроксимационные решения, которые работают быстрее, но они могут не соответствовать вашим потребностям.
Не решая проблему грубой силы (как уже упоминалось ранее), вы можете сначала отсортировать свои числа, а затем просмотреть оставшиеся возможные (поскольку после того, как вы передали значение Sum, вы не сможете добавить любое число, большее, чем Goal - Сумма).
Это изменит способ реализации вашего алгоритма (чтобы сортировать только один раз, а затем пропускать отмеченные элементы), но в среднем улучшит производительность.
public class Logic1 {
static int val = 121;
public static void main(String[] args)
{
f(new int[] {1,4,5,17,16,100,100}, 0, 0, "{");
}
static void f(int[] numbers, int index, int sum, String output)
{
System.out.println(output + " } = " + sum);
//System.out.println("Index value1 is "+index);
check (sum);
if (index == numbers.length)
{
System.out.println(output + " } = " + sum);
return;
}
// include numbers[index]
f(numbers, index + 1, sum + numbers[index], output + " " + numbers[index]);
check (sum);
//System.out.println("Index value2 is "+index);
// exclude numbers[index]
f(numbers, index + 1, sum, output);
check (sum);
}
static void check (int sum1)
{
if (sum1 == val)
System.exit(0);
}
}