CODEWITHSUNDEEP
javascriptjqueryarrays
MavrosGatos
MavrosGatos

Reputation: 529

How to divide a number into specific values contained in an array with javascript

2I have the following array of numbers and the following number:

var array= [0.5, 1, 2, 3, 5, 10, 15, 20, 30, 40, 50, 100, 150, 250, 500];
var number = 1845;

"desired result" --> [500, 500, 500, 250, 50, 40, 5]

I need to find a way to come up with the optimal combination of numbers included in the above array so that their addition creates the given number. The code must work this way because the acceptable numbers are only the ones in the array. So instead of 1845 I need to return 500,500,500,250,50,40,5.

This is my code but it doesn't work as I expect.

array = array.reverse();
var values = new Array();
var sts = $.inArray(number, array);
if (sts != -1){
    return number;
} else {
    for (k=0; k<array.length; k++){
        if ((number - array[k]) > 0){
            values.push(array[k]);
            number = number - array[k];
        }
    }
    return values.toString();
}

Upvotes: 0

Views: 84

Answers (3)

Roger
Roger

Reputation: 3256

The idea behind these problems is that you will want to check every possible solution in the smartest way possible. A* pathfinding is something you would need to learn in order to do this problem justice. Basically you tell the computer what data is the best to choose from in a list, then check if that is the answer. If it isn't the answer, then evaluate the cost to the next answer and repeat.

These type of questions have been around since before I was born. Getting to all 50 state capitols is one of those types of questions.

The long and short of it, is that you will need to recursively go through every solution until you have found the one that matches. the worst case scenario is O(2^n-1). The best case scenario is O(1).

Implementing the A* path finding algorithm or other similar types of cost/benefit algorithms will get you where you need to go faster. But you will need to learn how to implement them via JavaScript.

Upvotes: 0

MavrosGatos
MavrosGatos

Reputation: 529

I solved it. Here is the answer.

array = array.reverse();
var values = new Array();
var sts = $.inArray(number, array);
if (sts != -1){
    return number;
} else {
    function iter(){
        if ((number - array[k]) > 0){
            values.push(array[k]);
            number = number - array[k];
            iter();
        }
    }
    for (k=0; k<array.length; k++){
        iter();
    }
    return values.toString();
}

Upvotes: 0

Nina Scholz
Nina Scholz

Reputation: 386600

This proposal iterates all possible combinations of the given items and uses some short circuit for reducing the iterations/recursions.

It stops if the sum of the right side (a potential result set) is greater than the wanted sum and if sum of all items (left and right) is smaller than the wanted sum.

function getParts(array, sum) {
    function add(a, b) { return a + b; }

    function iter(left, right) {
        var sumRight = right.reduce(add, 0);
        left = left.slice();
        if (sumRight >= sum) {
            sumRight === sum && result.push(right);
            return;
        }
        if (!left.length || left.reduce(add, 0) + sumRight < sum) {
            return;
        }
        iter(left, right.concat(left.pop()));
        iter(left, right.concat([]));
    }

    var result = [];
    iter(array, []);
    result.sort(function (a, b) { return a.length - b.length; });
    return result;
}

function print(o) {
    document.write('<pre>length: ' + o.length + ' ' + JSON.stringify(o, 0, 4) + '</pre>');
}

print(getParts([0.5, 1, 2, 3, 5, 10, 15, 20, 30, 40, 50, 100, 150, 250], 5000));
print(getParts([0.5, 1, 2, 3, 5, 10, 15, 20, 30, 40, 50, 100, 150, 250], 495));

Upvotes: 1

Related Questions