Есть мост длина n и доски [1,2,3,8]. Построить мост наименьшим количеством использование досок
JS.Есть мост длина n, например 68м и доски чтобы построить мост. Длина досок разные и не знаем сколько их,например 1,2,3,8(м). Досок от каждого размера бесконечно , но нужно найти вариант чтобы построить мост наименьшим количеством использование досок.
function solve(arr, n) {
let res = [];
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length; j++) {
for (let k = 0; k < arr.length; k++) {
res.push(arr[i] + arr[j] + arr[k]);
}
}
}
res.forEach(e => { if(e == n) return e })
}
solve([1,2,3,8], 68);
код работает не так
Ответы (2 шт):
Жадный алгоритм (брать доски максимальной длины, сколько возможно, потом следующие) будет работать не для всех наборов данных. Например, для [1,6,10] и длины 12 жадный алгоритм даст 3, а правильно - 2.
А полноценно решить задачу можно с помощью динамического программирования - это задача о наборе суммы минимальным количеством монет.
Заведите массив A длиной n+1, заполните большим числом, кроме нулевой ячейки и для каждой длины доски L проверяйте ячейки, и обновляйте те, для которых A[i-L]+1 меньше текущего значения A[i]
Накатал такой вариант:
function Boards(arr, metr) {
arr = arr.sort(function (a,b){return (a + b)}); // Сортируем массив с длиной досок по убыванию
let width = metr, res = []; // Переменные для хранения данных
for(let i = 0; i < arr.length; i++) { // Проходим по массиву размеров досок
if(width > 0) { // Если общая длина моста ещё не закончилась, то:
let col = Math.floor(width / arr[i]); // Получаем количество досок, получая целое число от деления общей длины моста на длину доски.
if(col > 0) { // Если длина больше нуля, то:
res.push({ // Добавляем в массив, в котором будем хранить:
col: col, // количество досок
width: arr[i], // длина доски
fullwidth: (arr[i] * col) // общая длина
});
width = width - res[res.length-1].fullwidth; // Каждый раз вычетаем общую длину досок из длины моста.
} else continue; // Если количество меньше или равно нулю, то пропускаем эти доски и идём к следующим
} else break; // Если длина моста закончилась, то прерываем цикл.
}
// Выводим результат
console.info('Чтобы выложить мост длиной '+metr+'м нужно:');
for(let i = 0; i < res.length; i++) {
console.info('- '+res[i].col+' '+declOfNum(res[i].col, ['доска', 'доски', 'досок'])+', длиной '+res[i].width+'м, общая длина = '+res[i].fullwidth+'м');
}
} Boards([1,2,3,8], 68);
// Для красоты
function declOfNum(number,titles){
cases = [2,0,1,1,1,2];
return titles[(number%100>4 && number%100<20)? 2 : cases[(number%10<5)?number%10:5]];
}