Оптимальное разделение значения с использованием массива значений

ЭТА ПРОБЛЕМА

Представьте себе следующий сценарий:

Существует числовое значение, представляющее мощность:

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];

МОЙ ПОДХОД

Конечно, я пытался решить это сам, но из-за отсутствия математических вычислительных возможностей моего мозга я с треском провалился.

Мой подход был таким:

  1. Создайте массив, содержащий доступные мощности, отсортированные в порядке убывания.
  2. Зацикливайте общую требуемую мощность (копия w), пока общая мощность не станет равной 0 или ниже.
  3. Divide the total wattage requirement by the largest transformer available
    1. If division result is larger than 1, push the current transformer to the results array and subtract the current wattage from the total wattage
    2. Если результат деления меньше 1, сдвиньте массив преобразователей, чтобы удалить самый большой преобразователь в массиве.
  4. Если в массиве трансформаторов остался только один элемент, поместите его в массив результатов и установите для общей мощности значение 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;
        }

    }

}

person SquareCat    schedule 14.11.2014    source источник
comment
не могли бы вы опубликовать свой код?   -  person Nicolás Straub    schedule 14.11.2014
comment
Это довольно специфично, поэтому я хотел избежать этого, плюс я не чувствую, что у меня есть очень умный подход, и я уверен, что есть лучшие способы сделать это, но конечно. Сделаю за минуту.   -  person SquareCat    schedule 14.11.2014
comment
это кажется правильным ... не могли бы вы рассказать о случаях, когда это оказалось неправильным?   -  person Nicolás Straub    schedule 14.11.2014
comment
Похоже на проблему суммы подмножества с дополнительными требованиями, требующими найти наименьшее подмножество, которое решает ее оптимально . Я думаю, вам следует попытаться просто переборщить, если только ваше количество трансформаторов существенно не велико. Если это так, получайте удовольствие!   -  person Bergi    schedule 14.11.2014
comment
Наблюдение: решение, в котором вы используете только самый большой трансформатор, всегда приводит к минимальному количеству используемых трансформаторов, что является основным критерием. Сначала сделайте это, а затем замените один из них на самый маленький, который все еще может покрыть общую требуемую мощность. Затем попробуйте заменить следующий. Делайте это до тех пор, пока вы не сможете поменять местами. Должен гарантировать правильное решение.   -  person Saran    schedule 14.11.2014
comment
Звучит похоже на задачу о рюкзаке... возможно, вам стоит проверить алгоритм ее решения.   -  person chris-l    schedule 14.11.2014
comment
Пример A: я получаю [60, 18], когда я кормлю 83,2 (что означает, что есть непокрытый остаток. Пример B: я получаю [100, 18], когда я кормлю 124,8, хотя использование одной единицы 264 было бы более оптимальным решением Обратите внимание: я отредактировал доступные мощности в моем примере кода, чтобы они соответствовали моим реальным значениям.   -  person SquareCat    schedule 14.11.2014
comment
@chris-l Спасибо, проблема в том, что я не создан для этого. Мой мозг просто отказывается вычислять такие вещи. Я хорошо разбираюсь в программировании, но математика абсолютно не моя тема. Я очень старался решить эту проблему, но я больше не могу смотреть на проблему, она меня убивает :)   -  person SquareCat    schedule 14.11.2014
comment
@Берги Брутфорс? Не уверен, что вы имеете в виду под этим в данном случае. Количество трансформаторов не слишком велико. Сейчас максимум 5.   -  person SquareCat    schedule 14.11.2014
comment
@SquareCat: просто создайте все возможные подмножества, переберите их и найдите лучшее (у которого достаточно мощности и минимальное количество бывших в употреблении трансформаторов).   -  person Bergi    schedule 14.11.2014
comment
Эй, это довольно причудливый подход, ... на самом деле, я так и думал. Во-вторых, я понимаю, что это не вариант, потому что могут быть случаи, когда используется / требуется несколько трафов одинаковой мощности (например, когда вам нужно покрыть 2000 Вт). Так что этот способ не сработает :(   -  person SquareCat    schedule 14.11.2014
comment
Downvoter: если бы вы предоставили некоторую информацию о том, почему вы решили проголосовать против, это помогло бы мне И сообществу. ИМО, это было совершенно бессмысленное понижение.   -  person SquareCat    schedule 14.11.2014


Ответы (2)


не устанавливайте _wattageTotal в 0. Когда вы это сделаете, он выйдет из цикла while, и любой остаток, не охваченный вашим текущим _trafos, будет проигнорирован.

вам также необходимо изменить текущую мощность после проверки length =1 и проверить _wattageTotal > 0 в цикле while:

var wattages = [264, 100, 60, 35, 18];
var _wattageTotal = 82; // 1000 watts

var _trafos=new Array(); // for the results

console.log('-----------------------');
console.log('THESE ARE THE AVAILABLE WATTAGES:');
console.log(wattages);

while(_wattageTotal > 0){

    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( wattages[0] );
        _wattageTotal-=wattages[0];

    } else {

        console.log(wattages[0]+' DOES NOT FIT');

        if(wattages.length==1){
            _trafos.push(  wattages[0]  );
            _wattageTotal -= wattages[0];
        }

        wattages.shift();
    }

}

jsfiddle

person Nicolás Straub    schedule 14.11.2014
comment
Если вы посмотрите на мой код, я устанавливаю _wattageTotal в 0 только в том случае, если в массиве остался только один доступный трафик. Хотя вы правы в том, что на самом деле это проблема и этого делать не следует, это не решение проблемы как таковое (хотя бы так оно и было). В моих тестах результаты будут такими же, если я удалю эту строку. - person SquareCat; 14.11.2014
comment
кажется, я немного поторопился... обновляю ответ. - person Nicolás Straub; 14.11.2014
comment
Дает мне бесконечный цикл. - person SquareCat; 14.11.2014
comment
В вашей скрипке результат неверен. Там написано [60,18,18], но правильным выбором будет [100]. Как вы можете видеть, вычислить это очень сложно, и это не может быть просто решено методом проб и ошибок (был там, сделал это). Большое спасибо, хотя за вашу попытку помочь! - person SquareCat; 14.11.2014
comment
да, я так понял. решение довольно сложное и включает в себя проверку результата по сравнению с исходным массивом, чтобы увидеть, можете ли вы заменить более одного trafo другим trafo, и делать это рекурсивно, пока не останется доступных кандидатов для замены. Может быть, вы могли бы развить эту мысль. Я уже иду спать и с удовольствием сделаю это завтра утром... - person Nicolás Straub; 14.11.2014

После более глубоких исследований, тестирования, нескольких неудачных подходов и нескольких чашек кофе, вот окончательный результат.

// test values

var wattage=600;
var trafos=[264, 100, 60, 35, 18];

var g, i, results=[];

// since wattage can also end up below zero,
// we loop until it is no longer greater than zero

while(wattage>0){

    // each run, we want an empty array g

    g=[];

    // we iterate over all available trafos

    for (i in trafos){

        // g will contain our division factors, but since
        // we want to be able to sort this array, we must
        // use an object literal

        g.push({

            // g.k = the factor of the division (total wattage / trafo wattage)

            k: wattage/trafos[i],

            // g.v = the trafo wattage, as reference, so we know which 
            // division factor belongs to which trafo

            v: trafos[i]

        });

    }

    // now, g will contain the division factors for all trafo wattages
    // against the current wattage that needs to be covered
    // naturally these will range from 0 to X
    // we then use a sort function to sort this array
    // by which values are closest to 1 (= which trafos fit best for the current
    // wattage) but with the values SMALLER than 1 having more priority than
    // the ones being greater

    g.sort(function(a, b){
        var dis=Math.abs(1-a.k) - Math.abs(1-b.k);
        if(a.k<1 && b.k>=1){ return -1; }
        if(a.k>=1 && b<1){ return 1; }
        return dis;
    });

    // naturally, the first element of g will now contain the trafo
    // which covers best for the wattage that needs to be covered for,
    // so we push its wattage (using g.v) into the results array

    results.push( g[0].v );

    // finally we can now subtract the wattage from the total wattage
    // that still needs to be covered for

    wattage -= g[0].v;

}

ДОПОЛНИТЕЛЬНОЕ ОБЪЯСНЕНИЕ

Вместо использования сокращающегося массива. мы применяем другой подход: для каждого значения, которое мы проверяем и совпадаем, мы создаем массив, содержащий коэффициенты соответствующего деления.

Затем мы сортируем этот массив, используя довольно волшебную функцию сортировки, которая делает две вещи:

  • Он сортирует значения по тому, насколько близко значения к 1
  • с предпочтением значениям, которые меньше единицы, а не тем, которые больше

(За это спасибо пользователю BatScream, который предоставил эту функцию в ответ на мой вопрос Сортировка массива, по которому значение ближе всего к 1)

Первоначально я придумал это решение, используя функцию сортировки, но только сортируя значения, которые были ближе всего к 1. Это сработало, но все же привело к неоптимальным вычислениям, таким как это:

wattage = 600;
trafos=[264, 100, 60, 35, 18];

result = [264, 264, 60, 18];

Где лучшим результатом будет:

result = [264, 264, 100];

Поэтому цель состояла в том, чтобы соответствующим образом адаптировать функцию сортировки, чтобы она по-прежнему выбирала самый большой трафик, доступный для оставшейся мощности.

Теперь, когда мой мозг поджарился, я наконец могу покоиться с миром.

person SquareCat    schedule 14.11.2014