CODEWITHSUNDEEP
algorithmrounding
trainoasis
trainoasis

Reputation: 6720

Round number up to a certain combination of given values

I've been having a hard time solving this and also explaining it to people, but I will try: I have a float number and I want it rounded to the nearest combination of a few other given numbers.

I will now go straight into examples, otherwise I'm afraid I'll lose you:

Let's say our numbers to round up to are: 190, 290, 540, 1000

I'll provide some examples of given numbers and expected results just to make sure we are on the same page:

Given number: 54,6
Expected result: 190 (1x190)

Given number: 287,5
Expected result: 290 (1x290)

Given number: 575
Expected result: 580 (2x290) 

Given number: 1150 
Expected result: 1190 (1x1000 + 1x190)

Given number: 1955
Expected result: 2020 (1x1000 + 1x540 + 1x290 + 1x190)

Given number: 2875
Expected result: 3020 (2x1000 + 1x540 + 1x290 + 1x190)

So the point is to get the sum of values that equal or exceed the given number (and extract the one that exceeds the least?) I wrote a simple-minded function that somehow does what I want, but not exactly: 

function roundUpBasedOnPackaging(neededAmount, packagingIntegerArray) {

  console.log("We need to fill: " + neededAmount);

  var roundTo = 0;

  for (var len = packagingIntegerArray.length, i = len - 1; i >= 0; i--) {
    var currentItemGrams = packagingIntegerArray[i];

    //console.log("we are at " + currentItemGrams);

    if (roundTo + currentItemGrams <= neededAmount) {
      console.log("-- add: " + currentItemGrams);
      roundTo += currentItemGrams;
      i = len; // try this again
    }
    // if last and we'r not filled yet
    else if (i == 0 && roundTo < neededAmount) {
      console.log("-- add to get over neededAmount: " + currentItemGrams);
      roundTo += currentItemGrams;
    }

  }

  console.log("rounded to " + roundTo);

}

roundUpBasedOnPackaging(287.5, [190, 290, 540, 1000]);

You can clearly see what I did: loop from highest to lowest and add if the value is not equal or over our initial value. But this of course won't work in the example I provided (for value 287,5 since it would be much better to just choose 290 instead of two times 190).

It would be nice if I could get the algorithm to choose bigger numbers first and then use smaller ones.. but if you can provide a solution where smaller ones are used as a priority - that would be useful also.

I reckon I'd need a combination of sums to solve this - all possible combinations?!, but it would probably get messy. I don't mind a bit of recursion though...

Also, I think the second condition (else if) in my code is not really optimal - I'm sure there is a case where this wouldn't work properly and even go over the given value.

Any tips appreciated. Will work on my second solution until then :)

Upvotes: 1

Views: 84

Answers (3)

Alex Salauyou
Alex Salauyou

Reputation: 14338

Seems this problem is similar to Knapsack problem, which is NP-hard, but if initial weights have big enough common divisor, solution can be found in acceptable time using dynamic approach.

Let {K, N, M, ...} - set of initial weights, S - number we need to round up.

  1. Generate set of weights W = {K, 2K, 3K,..., (|S/K| + 1)*K, N, 2N, ..., (|S/N| + 1)*N, M, ...}, that will be used to fill up Knapsack. For repeating weights, select according to preference rule.

  2. Build dynamic sorted set of combinations D where items (combinations) are ordered by summary weight, tracking minimal extra weight equal or greater than S, in minExtra. On other words, minExtra is the best weight found so far.

Algorithm:

D = {};
minExtra = +inf 
for each (e in W) {                 // take next element from W
    for each (c in D) {             // iterate over existing combinations in D
        nw = c.weight + e.weight;   // weight resulting of adding e
        if (nw < minExtra) {
            D.put(nw, c.add(e))     // assign to nw copy of c with e added
            if (nw >= S)
               minExtra = nw;
        }
    }
    if (e.weight < minExtra) {   
        D.put(new C(e))             // put combination of only item e
        if (e.weight >= S)
            minExtra = e.weight
    }
}
return D.get(minExtra)

D.put() should accept element of existing weight if combinations of more items are preferred, or discard otherwise.

Upvotes: 1

user1196549
user1196549

Reputation:

If priority is given to the largest amounts and the given number may not be exceeded, the solution is straightforward.

Compute the number of times the largest amount fits (this is the quotient of the division) and deduce that.

Then repeat with the next largest,and so on.

1385: 1385/1000 = 1 => 385 remain
 385:  385/ 540 = 0 => 385 remain
 385:  385/ 290 = 1 =>  95 remain
  95:   95/ 190 = 0 => done.

Upvotes: 2

Karl
Karl

Reputation: 159

   Given number: 2875
   Expected result: 3020 (2x1000 + 1x540 + 1x290 + 1x190)

Expecting 10 × 290 = 2900 is closer. If that satisfies your rules.

If I'm right, this really makes me think of the Knapsack problem, although it's not exactly the same thing.

Edit. The algorithm you're looking if you need to have as many big numbers as possible could look like something like this:

-> fit as many 1000s as you can, save in "a"
-> take the smallest next number that makes the sum greater, save result in "b"
-> use the biggest number smaller than the "smaller next number" in previous step, add them in "a" until you can't fit them anymore
-> take the smallest next number that makes the sum greater, save result in "c"
-> etc.
-> return the closest value you end up with

If it does not perform well enough to your liking (the results are not good enough), then you'll need to weigh those numbers according to some arbitrary values, and that, that is exactly a knapsack problem.

Upvotes: -1

Related Questions