Saturday 10 June 2017

"Overpaying" a price with knapsack in node

I have this array of items with their prices (property is a random ID, value is the price itself):

var myItems = [{"10222689013":445.49},{"10421477049":54.21},{"10501187481":39},{"8387873996":39},{"10378860764":36.96},{"6260427541":31.83},{"10375621839":26.52},{"5263786797":25.13},{"10465039747":20.34},{"10479336223":18.93},{"10354237608":13.53},{"10384012706":12.22},{"10378859760":6.31},{"10350491915":5.75},{"10441942463":5.3},{"6232326311":4.36},{"7254487888":3.06},{"10274407041":2.84},{"10505002708":2.84},{"10505002635":2.84},{"10505002575":2.84},{"10505002983":2.84},{"10505002850":2.84},{"9558577114":2.84},{"9558577179":2.84},{"10093009482":2.84},{"10515811944":2.84},{"10515812014":2.84},{"10515812058":2.84},{"10093009494":2.84},{"10093009908":2.84},{"10093010135":2.84},{"10505002791":2.84},{"10093018649":2.84},{"10093018673":2.84},{"10515812127":2.84},{"10515812176":2.84},{"10515812216":2.84},{"10515812281":2.84},{"10515812344":2.84},{"10515812423":2.84},{"10093020096":2.84},{"10274407251":2.84},{"10274407222":2.84},{"10274407178":2.84},{"10274407146":2.84},{"10274407111":2.84},{"10274407084":2.84},{"10505002922":2.84},{"10274407017":2.84},{"10274406979":2.84},{"10274406951":2.84},{"10274406693":2.84},{"10274406675":2.84},{"10274406649":2.84},{"10274406619":2.84},{"10274406597":2.84},{"10274406562":2.84},{"9909942264":1.33},{"10501504755":0.54},{"9719056291":0.54},{"10423821338":0.54},{"10525934448":0.54},{"10454361875":0.54},{"10454362211":0.54},{"10501507364":0.54},{"10501507003":0.54},{"10525934421":0.54},{"9538738322":0.54},{"10501505461":0.54},{"10525934368":0.54},{"10501505076":0.54}]

I am trying to create a function that uses knapsack to overpay a given price. (Note that the classic knapsack principle will fill up a "bag" as far as possible, but it won't overfill it.)

I am currently using this module: https://www.npmjs.com/package/knapsack-js

var knapsack = require('knapsack-js');

function prepare(price){
    var result = knapsack.resolve(price, myItems);
    var totalPrice = 0;
    for(var i = 0; i < result.length; i++){
        var itemID = Object.keys(result[i])[0]
        var itemPrice = result[i][itemID]
        console.log("> ID: " + itemID + " | " + itemPrice.toFixed(2) + "$")
        totalPrice += itemPrice;
    }
    console.log(">>>> Total price: " + totalPrice.toFixed(2))
}

prepare(21) 

This will give this output:

> ID: 10515812423 | 2.84$
> ID: 10093020096 | 2.84$
> ID: 10354237608 | 13.53$
> ID: 10501507364 | 0.54$
> ID: 10501507003 | 0.54$
> ID: 9719056291 | 0.54$
>>>> Total price: 20.83

So with this as an example:
20.83 is the "cheapest" combination of items that will still fit into the 21 I gave to the function.

What I am trying to do is however, have the "cheapest" combination that is ABOVE the given number. It could add another one of the cheapest items (0.54) so the price would be 21.37, which is greater than 21.

This can surely be done by removing all the objects that were used with knapsack from the original array, calculate the price-difference and then loop through the array and add the first item that is greater than the difference.

But there musst be a more efficient way, right?



via Thomas Weiss

No comments:

Post a Comment