Optimally sectioning a value using an array of values

Question

THE PROBLEM

Imagine the following scenario:

There is a numeric value representing a wattage:

var w = 1000; // 1000 watts

Then there is an array containing a variety of transformers, covering certain wattages:

var transformers = [240, 200, 100, 50, 20];

The goal is to create an array that contains any number of values from transformers needed to cover for the wattage needs as defined per w.

However, the resulting array must contain as few elements as possible, thus large numbers come first. However, there must also be minimal loss, so whatever is left over from division, should be covered by the smallest amount (from transformers) as possible.

The goal is simply to compute the transformers needed to cover for the supplied wattage, with minimal loss (use a smaller transformer when possible, but use the fewest amount of transformers altogether).

EXAMPLE 1

w = 1000;
transformers = [260, 200, 100, 50];
results = [260, 260, 260, 260];

EXAMPLE 2

w = 1042;
transformers = [260, 200, 100, 50];
results = [260, 260, 260, 260, 50];

EXAMPLE 3

w = 502;
transformers = [220, 180, 60, 30];
results = [220, 220, 180];

MY APPROACH

Of course i tried to solve this myself, but due to a lack of mathematical computing capabilities of my brain, i failed miserably.

My approach was this:

1. Create an array that contains the available wattages, sorted in descending order
2. Loop over a total wattage requirement (a copy of w) until the total wattage is 0 or lower
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. If division result is smaller than 1, shift the array of transformers to remove the largest transformer in the array
4. If array of transformers has only one element left, push that to the results array and set the total wattage to 0

The results came close to correct, but in some cases turned out to be wrong as more optimal choices for covering the wattage could have been made. I also had cases when there was uncovered for wattage left.

My Code

// 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;
        }

    }

}

Answer 1

don't set _wattageTotal to 0. When you do it exits the while loop, and any leftover not covered by your current _trafos will be ignored

you also need to shift the current wattage after performing the check for length =1, and check for _wattageTotal > 0 in your while loop:

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

Answer 2

After more in-depth research, testing, some failed approaches and a number of coffees, here's the final result.

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

}

ADVANCED EXPLANATION

Instead of using a shrinking array. we take a different approach: for each value we check and match we create an array that contains the factors of the corresponding division.

We then sort that array using a pretty magic sort function which does two things:

• It sorts values by how close the values are to 1
• with a preference to values that are smaller than one, rather than those that are greater

(Credits for this go to user BatScream who provided this function in response to my question Sorting an array by which value is closest to 1)

I initially came up with this solution using the sort function, but only sorting the values by which ones were closest to 1. This worked, but still resulted in non-optimal computations such as this:

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

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

Where as the best result would be:

result = [264, 264, 100];

Therefore the goal was to adapt the sort function accordingly, so that it would still pick the largest trafo available for the still to-cover-for wattage.

Now that my brain is fried, i can finally rest in peace.