Как реализовать алгорим задачи о сумме подмножеств?
Дано множество вещественных чисел N. Задача заключается в нахождении (одного достаточно) подмножества N, чтобы сумма чисел этого подмножества равнялась S. Числа могут быть отрицательными, а также повторяться.
Пробовал решить перебором, но количество чисел достаточно большое(330 штук) и в этом столетии мне не успеть посчитать. Видел решения с помощью динамического программирования, но они либо не поддерживают отрицательные числа, либо не поддерживают повторяющиеся числа. Что делать - не знаю
p.s Числа в множестве N могут повторяться. пример N = {1, 1 , 2, 5}
Demond98, не могли бы Вы внести ясность, как понимать фразу "Числа могут быть отрицательными, а также повторяться."?
множество может содержать одинаковые числа
или
числа из множества можно повторять сколько угодно раз
Если задать 330 значений, ждать можно очень долго, возможно день, возможно год, надо считать :) (максимально возможное число вариантов которое будет перебирать алгоритм будет запредельно)
Поэтому в примере задал множество включающее всего 30 элементов.
код:
/**
* готовим исходные данные (рандомно:)
*/
// искомая сумма, генерируем случайное целое число в диапазоне от 0 до 100.
var S = Math.floor(Math.random()*50);
// массив в котором хранится подмножество
var N = [];
// заполняем его случайными целыми числами в диапазоне от -s до +s
for( var i=0; i<30; i++){
N[i] = Math.floor(Math.random()*S*2)-S;
}
/**
* перебираем (в случае большого числа элементов в N может быть критично по памяти :)
*/
// начинаем поиск (алелуя :)
console.log("искомая сумма: ("+S+")");
console.log("множество значений:\n("+N.join(", ")+")\n");
searchSubN(S, N, [])
// рекурсивная функция (производит полный перебор всех вариантов)
function searchSubN(S, N, sub) {
// начинаем перебор
N.forEach((c,i)=>{
// клонируем массив решений
var cloneSub = sub.slice();
if(c===S){
// найдено очередное решение
cloneSub.push(c);
// выводим сообщение
console.log("найдено решение: summ("+cloneSub.join(", ")+") = "+cloneSub.reduce( (a,c)=>{return a+c;} ) );
}else if(c<S){
// возможно это станет решением
cloneSub.push(c);
// делаем клон массива
var clone = N.slice();
// удаляем из клона текущий элемент
clone.splice(i,1);
// ищем следи оставшихся подмножество равное S-c
searchSubN(S-c, clone, cloneSub);
}
});
}
Отрицательные числа, конечно, здорово портят задачу ;) классические переборные алгоритмы такой подлянки не имеют.
Но общую логику имеет смысл сохранить: ваша цель - определенная сумма, можно к ней стремиться. На каждом шаге подбора варианты сортируются по тому, насколько их прибавление приближает вас к искомой сумме (по модулю). И перебор до тех пор, пока первое же число не дает разность 0.
Adamos к сожалению решение задачи путем перебора на практике затруднительно, число вариантов растет с прогрессией, равной сумме всех n!/(k!*(n-k)!)
где:
n - число элементов в множестве
k - принимает значения от 1 до n
тоесть для n=330 число перебираемых вариантов будет настолько велико, что я его даже посчитать не могу:)
var n = 330;
var v = 0;
for(var k=1; k<=n; k++){
v+=factorial(n)/(factorial(k)*factorial(n-k));
}
console.log(v);
function factorial(n){
var result = 1;
while(n){
result *= n--;
}
return result;
}
Роман, к счастью, задача упрощается двумя моментами:
1. Не нужно искать все варианты. Достаточно попытаться найти хоть один, именно для этого оптимизируется выбор на каждом шаге.
2. По условиям задачи, можно смело прореживать исходные данные, выкидывая числа, получаемые суммой других чисел.
Ну, и математика нам на что дана? Если число не простое, то достаточно найти пару-тройку чисел, дающих в сумме один из его множителей. Собственно, если среди чисел есть положительное и отрицательное, отличающееся по модулю на единицу, перебор можно вовсе не затевать ;)
Adamos,
1. согласен
2. согласен (хотя в случае с отрицательными числами может возникнуть проблема выбора)
НО по моему каждое число из исходного множества можно использовать лишь один раз в каждом конкретном решении, так что перебор делать придется:)
PS: сейчас спрошу у автора что имелось ввиду под фразой "Числа могут быть отрицательными, а также повторяться."
- по моему то что числа в множестве могут повторятся
- по вашему то что числа из множества можно повторять
если прав я - то перебор
если вы - то эвристики (предложенные вами и множество других)
Роман, .. разве что подключиться к экспериенсу?.. но это уже от наличия времени )).. одно дело вечером лясим-трясим, другое - хоть маленько творчески подумать...
однако напомню, задача уже давно определена как не тривиальная для попыток быстрого решения
Обычная динамическое программирование работает для повторяющихся чисел, тут не должно быть проблем. Отрицательные числа решаются просто - считаете все возможные суммы только положительных чисел стандартной динамикой и отдельно только для отрицательных чисел (опустив знак). Потом одним циклом перебираете сумму положительных чисел x>=S и смотрите, если x-S можно набрать отрицательными числами. На общую сложность этот цикл не влияет.
Вас приятно почитать: всегда найдётся косячек )
Пусть есть набор {2,4,8,...2^330, -1} всего-то 330 чисел, S=1
Поехали:
Cчитаем все возможные суммы только положительных чисел стандартной динамикой - а это 2^330 чисел, и все четные! Долго считать будем?
Очевидно, что в задаче ограничения на сами числа небольшие (хоть автор и не указал). Иначе задача не имеет решения, которое можно выполнить до тепловой смерти вселенной.
Средний
