ЭТА ПРОБЛЕМА
Представьте себе следующий сценарий:
Существует числовое значение, представляющее мощность:
var w = 1000; // 1000 watts
Затем есть массив, содержащий множество трансформаторов, охватывающих определенные мощности:
var transformers = [240, 200, 100, 50, 20];
Цель состоит в том, чтобы создать массив, содержащий любое количество значений из transformers
, необходимых для покрытия потребностей в мощности, как определено для w
.
Однако результирующий массив должен содержать как можно меньше элементов, поэтому сначала идут большие числа. Однако потери также должны быть минимальными, поэтому все, что останется от деления, должно быть покрыто как можно меньшей суммой (от transformers
).
Цель состоит в том, чтобы просто вычислить трансформаторы, необходимые для покрытия поставляемой мощности, с минимальными потерями (по возможности используйте меньший трансформатор, но в целом используйте наименьшее количество трансформаторов).
ПРИМЕР 1
w = 1000;
transformers = [260, 200, 100, 50];
results = [260, 260, 260, 260];
ПРИМЕР 2
w = 1042;
transformers = [260, 200, 100, 50];
results = [260, 260, 260, 260, 50];
ПРИМЕР 3
w = 502;
transformers = [220, 180, 60, 30];
results = [220, 220, 180];
МОЙ ПОДХОД
Конечно, я пытался решить это сам, но из-за отсутствия математических вычислительных возможностей моего мозга я с треском провалился.
Мой подход был таким:
- Создайте массив, содержащий доступные мощности, отсортированные в порядке убывания.
- Зацикливайте общую требуемую мощность (копия
w
), пока общая мощность не станет равной 0 или ниже. - Divide the total wattage requirement by the largest transformer available
- If division result is larger than 1, push the current transformer to the results array and subtract the current wattage from the total wattage
- Если результат деления меньше 1, сдвиньте массив преобразователей, чтобы удалить самый большой преобразователь в массиве.
- Если в массиве трансформаторов остался только один элемент, поместите его в массив результатов и установите для общей мощности значение 0.
Результаты были близки к правильным, но в некоторых случаях оказались неправильными, поскольку можно было бы выбрать более оптимальный вариант покрытия мощности. У меня тоже были случаи, когда не накрывалась ваттность.
Мой код
// test values:
var wattages = [264, 100, 60, 35, 18];
var _wattageTotal = 1000; // 1000 watts
var _trafos=new Array(); // for the results
console.log('-----------------------');
console.log('THESE ARE THE AVAILABLE WATTAGES:');
console.log(wattages);
while(_wattageTotal){
console.log('WATTAGE TOTAL: '+_wattageTotal);
console.log('TESTING: '+wattages[0]+' against total wattage => '+_wattageTotal/wattages[0]);
if( _wattageTotal/wattages[0] >= 1 ) {
console.log('==> FOUND FIT: '+wattages[0]);
_trafos.push( byWattage[ wattages[0] ].key );
_wattageTotal-=wattages[0];
} else {
console.log(wattages[0]+' DOES NOT FIT');
wattages.shift();
if(wattages.length==1){
_trafos.push( byWattage[ wattages[0] ].key );
_wattageTotal=0;
}
}
}