# Find the best matching combination of numbers

Posted on

Problem

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=> {
});
``````

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 => {
})
})

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
const perc =
total += perc
})
})
})

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

Array.from(Array(10)).forEach(() => {
Object.keys(percentages).forEach(chunkId => {
let highestPropId
let highestPropPercentage = 0
if (perc > highestPropPercentage) {
highestPropPercentage = perc
highestPropId = propId
}
})
const remainingNum = requirements[highestPropId] - myTotal[highestPropId]
const koe = 0.5
const multiplier =
Object.keys(myTotal).forEach(propId => {
})
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?

• 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.

Solution

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

• 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 =
``````
• 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`).

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
const perc =
total += perc
})
})
})
``````
``````myTotal { a: 500.3204153326983, b: 1200.0002333151795, c: 1499.7678177477337 }
``````

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