Javascript - how can I optimize this script?

Question

Backstory

I have a set of data which is a list of product prices and a target number I need to come close to. I've theorized that the quickest way to do this is to generate every possible purchase set and then see which outcome is the closest to my target number.

eg.

example data set: $10, $5, $1
example target: $12
boolean "possibles": 001, 010, 100, 011, 101, 110, 111
possible sums: $1, $5, $10, $6, $11, $15, $16
the closest matching boolean set is 101 for $11

Question

Most data sets are minimal so using es6 is just fine. As the data increases the processing time grows exponentially as expected. Short of choosing a different language, what advancements could I make to shave off time?

Here's the dataset that I'm currently struggling with:

data: [7524.00,1.63,2000.00,23794.00,0.01,330.00,462.00,858.00,5000.00,5250.00,23162.00,23804.00,5250.00,13376.00,0.06,0.08,4000.00,10000.00,166.56,12441.00,25.00,1000.00,20000.00,2000.00,20000.00,10000.00,5468.00,20000.00];
target 201887

code

jsfiddle

let possibles = [];
let sums = [];
let target = 201887;
let data = [7524.00,1.63,2000.00,23794.00,0.01,330.00,462.00,858.00,5000.00,5250.00,23162.00,23804.00];//,5250.00,13376.00,0.06,0.08,4000.00,10000.00,166.56,12441.00,25.00,1000.00,20000.00,2000.00,20000.00,10000.00,5468.00,20000.00];

let rep = new Array(data.length).fill(1).join('');

let decMax = b2d(rep) + 1;

genPossibles(decMax, possibles)
.then(genSums()
.then(matchTarget()));

/****************
    functions
****************/

function d2b(d){
    return Number(d).toString(2);
}
function b2d(b) {
    return parseInt(b, 2);
}

function genPossibles(decMax, arr, start=0, runs=1000) {
    return new Promise((resolve, reject) => {
    //console.log(decMax, arr.length, start, runs);
    for(let i = start; i < start+runs; ++i) {
      if(start+i > decMax) {
        possibles.pop(); // last item is useless
        console.log("possibles", possibles.length);
        resolve();
        return;
      }

      let binStr = d2b(i);
      possibles.push(binStr);
    }

    setTimeout(() => genPossibles(decMax, arr, start+runs), 0);
  });
}
function genSums(start=0, runs=1000) {
    return new Promise((resolve, reject) => {
    for(let i = start; i < start+runs; ++i) {
      if(i >= possibles.length) {
        console.log("sums", sums.length);
        resolve();
        return;
      }

      let str = possibles[i];
      let sum = 0;
      str.split('').reverse().forEach((bool, j) => {
        if(bool == 1) sum += +data[j];
      });
      sums.push(sum);
    }

    setTimeout(() => genSums(start+runs), 0);
  });
}
function matchTarget() {
    let closest = {id:-1, bin: '', total:-1, diff:Infinity};
    sums.forEach((o, i) => {
      let d = Math.abs(target - o);
      if(d < closest.diff) {
        closest.id = i;
        closest.bin = possibles[i];
        closest.total = o;
        closest.diff = d;
      }
    });
    console.log("closest", closest);
}

additional fyi

I have the data commented out about half way until I figure out how to make this run quicker.

Javascript - how can I optimize this script?

0 Answers