У меня есть массив, нужно найти все варианты сложения элементов массива, которые равны 1000.
1000 = 500 + 500
1000 = 500 + 200 + 200 + 100
1000 = 500 + 200 + 100 + 100 +100
Пример:
let number = 1000;
let array = [100, 200, 500];
Stack Overflow на русском — это сайт вопросов и ответов для программистов. Присоединяйтесь! Регистрация займёт не больше минуты.
Присоединиться к сообществуУ меня есть массив, нужно найти все варианты сложения элементов массива, которые равны 1000.
1000 = 500 + 500
1000 = 500 + 200 + 200 + 100
1000 = 500 + 200 + 100 + 100 +100
Пример:
let number = 1000;
let array = [100, 200, 500];
Может перемудрил, но код рабочий!
Суть подхода - перебор всех возможных вариантов сочетаний.
Варианты сочетаний можно представить в виде битовых карт. Например: 8 это 2^3 то есть три бита 111 дает следующие сочетания для массива [500,200,100]
:
000, 001, 111, 010, 011, 100, 110, 101.
Подставьте вместо каждой единички соответствующее (по index) значение и получится:
[], [100], [500,200,100], [200], [200,100],[500], [500,200], [500,100].
Если б числа не повторялись, то было бы 8 вариантов, отбрасываем 000 - 7 вариантов.
Чтобы перебрать все варианты, сначала наполняем массив значениями, так, чтобы сумма каждого в отдельности множества элементов не превышала итог:
[500,500, 200,200,200,200,200, 100,100,100,100,100,100,100,100,100,100]
И получаем, что вариантов сочетаний этих элементов 2^17 - 1 (все 0), то есть 1<<17 - 1, то есть: 11111111111111111 в битовом выражении (не включая все 0).
Дальше проходимся по этим битовым маскам и заменяем 1 в маске, на соответствующие значения (по индексу) в массиве. Сравниваем их сумму с необходимым итогом и записываем или нет в variants
их строковое представление ( для Set каждый отдельный объект является уникальным, поэтому сами одинаковые (для нас) массивы он не отбрасывает).
let number = 1000;
let array = [500, 200, 100];
array.sort((a,b) => a - b); // сортируем в обратном порядке
let arr = []; // пустой массив для получения всех элементов, которые можно поместить в number
array.forEach( a => {// Дополняем массив повторными значениями, сумма которых не превышает number
for(let i=0; i< Math.floor(number/a); i++){
arr.push(a);
}
});
let variantsNum = 1 << arr.length; // Считаем количество вариантов
let variants = new Set(); // Объявляем Набор для неповторяющихся элементов
for(let i=1; i < variantsNum; i++){ // Перебираем все варианты, формируя битовые карты для подстановок
let n = variantsNum;
let count = arr.length;
let variant = [];
while(n > 0){
if(i & n) variant.push(arr[count]); // Ищем 1 в битовой карте
n = n >> 1; // Смещаем на один разряд
count--;
}
if(sum(variant) == number){ // Если равно number, то добавляем строку
variants.add(variant.join()); // Строку в дальнейшем можно преобразовать в массив
}
}
function sum(arr){
return arr.reduce((a,b) => a + b);
}
console.log([...variants]); // ВЫВОДИМ РЕЗУЛЬТАТ РАБОТЫ
Помимо этого выложу и переработанный код, предложенный MBo
. В нем задается массив деталей определенной длины и количество каждой из них. Функция берет количество деталей в этом пределе. Может, кому пригодится.
class Detail { // Создаем класс для деталей
constructor(len, num){
this.len = len;
this.num = num;
}
}
let details = [ // Забиваем массив новыми деталями, порядок не важен, позже будет сортировка
new Detail(1400,3),
new Detail(1100,4),
new Detail(1000,4),
new Detail(1050,4),
new Detail(1010,4),
new Detail(900,4),
new Detail(800,4),
new Detail(700,4),
new Detail(500,10),
new Detail(400,8),
new Detail(300,10),
new Detail(200,4)
]
details.sort((a,b) => a.len - b.len); // Сортировка по возрастанию `len`
let variants = []; // Здесь будут накапливаться все варианты
function getAllChains(dets, sum, last, l){
// Для себя в этом месте я добавил проверку на длину массива и добавлял все варианты (в моем случае не надо ждать совпадения с суммой, она маловероятна)
//if(l.length > 0){
// variants1.push(l);
// } else
if(sum == 0){ // Скидываем накопленный массив, если остаток 0
variants.push(l);
return;
}
for(let i = last; i < dets.length; i++){
if(dets[i].len > sum || dets[i].num == 0) break; // Дополнительно проверяем наличие деталей
dets[i].num--; // Убавляем количество текущей детали
let l1 = [...l];
l1.push(dets[i].len);
getAllChains(dets, sum - dets[i].len, i, l1);
dets[i].num++; // Возвращаем после рекурсии
}
}
getAllChains(details, 2700, 0, []);
console.log(`Variants' num: ${variants.length}`);
console.log(variants);
Можно на каждом шаге сводить задачу к меньшей размерности.
Например, с помощью рекурсии
(Варианты составить сумму 1000) =
([500] + Варианты составить сумму (1000 - 500)) +
([200] + Варианты составить сумму (1000 - 200)) +
([100] + Варианты составить сумму (1000 - 100)) +
Пример. Начало цикла с индекса last позволяет избежать повторов.
let variants = []
//arr сортирован
function parts(arr, sum, last, l){
if(sum == 0){
//console.log(l);
variants.push(l);
return;
}
for(let i = last; i < arr.length; i++){
if(arr[i] > sum) break;
parts(arr, sum - arr[i], i, l + " "+arr[i]);
}
}
parts([100,200,500], 1000, 0, "");
console.log(variants);
Кроме того, в определённых условиях выгодно хранить уже сгенерированные варианты для сочетаний параметров (sum, набор) и использовать их (нужна память, конечно)
let arr = [1,3,7]; let sum = 15; function parts(arr, sum, last, l){ if(sum < 0){ return l; } for(let i = last; i < arr.length; i++){ if(arr[i] > sum) break; l.push(arr[i]); parts(arr, sum - arr[i], i, [...l]); } } let variants = parts(arr, sum, 0, []); console.log(variants);
Что не так? Не работает у меня, синтаксис не знакомый. jsfiddle.net/efimleonid/owkvbf3y/11
– Leonid
29 мар '20 в 11:40
l.push(arr[i])
неверно, т.к. элемент нужн добавлять к копии списка, которая передаётся на следующий уровень рекурсии. Однако можно и модифицировать единственный список, но после возврата из рекурсии удалять то, что добавляли.
– MBo
29 мар '20 в 13:03