Алгоритм для нахождения, который числа из списка размера n суммируют к другому числу
Я попробовал вышеуказанное решение, но я счел его непригодным для больших объемов данных. Затем я обнаружил функцию потока:
MongoClient.connect("...", function(err, db){
var c = db.collection('yourCollection');
var s = c.find({/* your query */}).stream();
s.on('data', function(doc){
c.update({_id: doc._id}, {$set: {name : doc.firstName + ' ' + doc.lastName}}, function(err, result) { /* result == true? */} }
});
s.on('end', function(){
// stream can end before all your updates do if you have a lot
})
})
6 ответов
Интересные ответы. Спасибо за указатели на Википедию - пока интересный - они на самом деле не решают проблему, столь установленную, как я искал точные совпадения - больше проблемы балансировки учета/книги, чем традиционная упаковка мусорного ведра / задача о ранце.
Я следовал за разработкой переполнения стека с интересом и задался вопросом, насколько полезный это будет. Эта проблема подошла на работе, и я задался вопросом, могло ли переполнение стека предоставить готовый ответ (или лучший ответ) более быстрый, чем я мог записать это сам. Спасибо также за комментарии, предлагающие это быть отмеченной домашней работой - я предполагаю, что это довольно точно в свете вышеупомянутого.
Для тех, кому интересно, вот мое решение, которое использует рекурсию (естественно), я также передумал о сигнатуре метода и пошел для Списка>, а не десятичное число [] [] как тип возврата:
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-трудным.
Не решая проблему грубой силы (поскольку другие уже упомянули) Вы могли бы хотеть отсортировать свои числа сначала и затем пробежаться через возможные оставленные (так как, после того как Вы передали значение Суммы, Вы не можете добавить число, больше, чем Цель - Сумма).
Это изменит способ, которым Вы реализуете свой алгоритм (чтобы отсортировать только однажды и затем пропустить отмеченные элементы), но в среднем улучшил бы производительность.
Вы описали задачу о ранце, единственным истинным решением является грубая сила. Существуют некоторые решения для приближения, которые быстрее, но они не могли бы соответствовать Вашим потребностям.
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);
}
}