Find the best matching combination of numbers

Question

I need to manipulate chunks quantity until total will be as close as possible to the requirements. Decimals are ok in the quantity.

Again: I can change only quantity property.

So if the requirements are {a:500; b:1200; c:1500}, then the quantity field in the chunks array should be changed so that when I run this:

// sum all chunks
Object.keys(chunks).forEach(chunk=> {
  Object.keys(total).forEach(id=> {
    total[id] += chunks[chunk].payload[id] * chunks[chunk].quantity
  });

It returns an object as close as possible to {a:500; b:1200; c:1500}.

How do I do that efficiently?

const chunks = { // <- the chunks
  chunk1: {
    quantity: 0, // <- the quantity
    payload: { a: 19, b: 17, c: 10 } 
  },
  chunk2: {
    quantity: 0, // <- the quantity
    payload: { a: 17, b: 11, c: 15 } 
  },
  chunk3: {
    quantity: 0, // <- the quantity
    payload: { a: 7, b: 19, c: 0 } 
  },
  chunk4: {
    quantity: 0, // <- the quantity
    payload: { a: 14, b: 4, c: 19 } 
  },
  chunk5: {
    quantity: 0, // <- the quantity
    payload: { a: 3, b: 15, c: 6 } 
  },
  chunk6: {
    quantity: 0, // <- the quantity
    payload: { a: 10, b: 16, c: 3 } 
  },
  chunk7: {
    quantity: 0, // <- the quantity
    payload: { a: 2, b: 3, c: 2 } 
  },
  chunk8: {
    quantity: 0, // <- the quantity
    payload: { a: 14, b: 16, c: 11 } 
  },
  chunk9: {
    quantity: 0, // <- the quantity
    payload: { a: 7, b: 2, c: 2 } 
  },
  chunk10: {
    quantity: 0, // <- the quantity
    payload: { a: 1, b: 7, c: 17 }
  }
}

const requirements = { // <- the requirements
  a: 500,
  b: 1200,
  c: 1500
}

const total = {
  a: 0,
  b: 0,
  c: 0
}

// sum all chunks
Object.keys(chunks).forEach(chunkId => {
  Object.keys(total).forEach(propId => {
    total[propId] += chunks[chunkId].payload[propId] * chunks[chunkId].quantity
  })
})

console.log(total) // <- i need this to be as close as possible to the `requirements`.

// MY SOLUTION:
const percentages = JSON.parse(JSON.stringify(chunks))
Object.keys(percentages).forEach(chunkId => {
  let total = 0
  Object.keys(percentages[chunkId].payload).forEach(propId => {
    const perc =
      percentages[chunkId].payload[propId] / (requirements[propId] / 100)
    percentages[chunkId].payload[propId] = perc
    total += perc
  })
  Object.keys(percentages[chunkId].payload).forEach(propId => {
    percentages[chunkId].payload[propId] =
      percentages[chunkId].payload[propId] / (total / 100)
  })
})

const myTotal = {
  a: 0,
  b: 0,
  c: 0
}

Array.from(Array(10)).forEach(() => {
  Object.keys(percentages).forEach(chunkId => {
    let highestPropId
    let highestPropPercentage = 0
    Object.keys(percentages[chunkId].payload).forEach(propId => {
      const perc = percentages[chunkId].payload[propId]
      if (perc > highestPropPercentage) {
        highestPropPercentage = perc
        highestPropId = propId
      }
    })
    const remainingNum = requirements[highestPropId] - myTotal[highestPropId]
    const koe = 0.5
    const multiplier =
      (remainingNum / chunks[chunkId].payload[highestPropId]) * koe
    Object.keys(myTotal).forEach(propId => {
      myTotal[propId] += chunks[chunkId].payload[propId] * multiplier
    })
    chunks[chunkId].quantity += multiplier
  })
})

console.log('myTotal', myTotal)
/*
in the console log output you'll see this:
{
  "a": 499.98450790851257,
  "b": 1202.1742982865637,
  "c": 1499.5877967505367
}
compare it with the `requirements` object above:
const requirements = { // <- the requirements
  a: 500,
  b: 1200,
  c: 1500
}
as you see, it's almost the same. I need more efficient solution
*/

It's not accurate and quite inefficient. Any better options?

Notes, answering the first comment:

• Second snippet contains first snippet and my solution.
• The quantity is a property in chunks object. Find it in the very beginning of the first snippet
• "As close as possible" means as close to requirements as mathematically possible.
• Input is in the first code snippet. To get output, pls run the first snippet.

Answer 1

From a short review;

• Your code is really hard to read/parse, I would not want to maintain this

• You have no useful comments, // <- the quantity is not useful

• You should terminate your lines with ;,

• I don't know if you have control over how you get the data, but getting it as an object is not helpful, this would be much easier/readable if you got a list instead

• In fact, this code is full of functional programming on objects, if you really want to do this, you should convert your objects to lists first

• Array(10) <- You hardcoded 10, at least go for Object.keys(chunks).length

• koe is an unfortunate variable name, why is it 0.5? (See lack of comments)

• In a solution driven approach, you should probably never enumerate over the keys of the payload (Object.keys(percentages[chunkId].payload).forEach), the payload could have more fields than the solution

• This should be 1 line

  const perc =
    percentages[chunkId].payload[propId] / (requirements[propId] / 100)
  

• I see this as a Knapsack problem, which is NP-hard, meaning that getting the perfect result will always be slow, in fact I see this as a multi-dimensional knapsack problem which is even harder than the regular knapsack problem.

From the comments, if we think of (a,b,c) as (length, width, height) and requirements as a bag of size (500, 1200, 1500). Then the question is how can we best (best as, least space wasted) fill the bag with different chunks (they all have their size defined in payload).

Answer 2

You can replace this entire block of code with const percentages = chunks; and your results more precisely match the requirements:

// MY SOLUTION:
const percentages = JSON.parse(JSON.stringify(chunks))
Object.keys(percentages).forEach(chunkId => {
  let total = 0
  Object.keys(percentages[chunkId].payload).forEach(propId => {
    const perc =
      percentages[chunkId].payload[propId] / (requirements[propId] / 100)
    percentages[chunkId].payload[propId] = perc
    total += perc
  })
  Object.keys(percentages[chunkId].payload).forEach(propId => {
    percentages[chunkId].payload[propId] =
      percentages[chunkId].payload[propId] / (total / 100)
  })
})

myTotal { a: 500.3204153326983, b: 1200.0002333151795, c: 1499.7678177477337 }

Previously your result was:

myTotal { a: 499.98450790851257, b: 1202.1742982865637, c: 1499.5877967505367 }

For the record, I still have no idea what you're trying to do.

manipulate chunks quantity until total will be as close as possible to the requirements

Then why not just add the difference so they are equal?