Sunday, 28 March 2021

Finding the best possible subset combinations of numbers to reach a given sum or closest to it

So, I have this problem I need to solve, apparently this is called Subset Sum Problem, except I need to get the subset not only when is exact to the given number, but the closest in case there is no exact sum that reaches the given number, it shouldn’t go over the reference number, only below, also if there are more than two possible subsets with the same result, I'd like to get the subset with the better distribution, from the highest to lowest number in the array as preferred, and limiting each subset to not overpass 10 times the same number, repeating is allowed, for example:

Here is the array with the predefined values:

let num = [64.20, 107, 535, 1070];

and a given number:

let investment = 806.45

One possible solution would be:

[0, 2, 1, 0] // this sums up to 749 (since there is no way to get to 806.45 with the given array)

Please notice this result is referring to how many times each value in nums is allowed to reach the sum:

But a better solution would be:

[4, 5, 0, 0] // this sums up to 791.80 (since there is no way to get to 806.45 with the given array)

And an even better solution (because takes in consideration the higher values over the lower ones first)

[4, 0, 1, 0] // this sums up to 791.80 also but you can see it's taking a higher value when possible.

Another important restriction would be that should never give a negative result.

So far i have tried like this (in VueJS):

getPackages(){
      let investment = 806.45;
      const num = [64.20, 107, 535, 1070]
      let a, b, c, d;
      let results = [];

      a = investment / num[0] >= 0 ? (investment/num[0]) : 0;
      b = investment / num[1] >= 0 ? (investment/num[1]) : 0;
      c = investment / num[2] >= 0 ? (investment/num[2]) : 0;
      d = investment / num[3] >= 0 ? (investment/num[3]) : 0;

      let dResult = [], cResult = [], bResult = [], aResult = [];

      for (let i = 0; i <= d; i++){
        if (i>0){
          dResult.push((i * num[3]))
        }
      }

      for (let i = 0; i <= c; i++){
        if (i>0){
          cResult.push((i * num[2]))
        }
      }

      for (let i = 0; i <= b; i++){
        if (i>0){
          bResult.push((i * num[1]))
        }
      }

      for (let i = 0; i <= a; i++){
        if (i>0){
          aResult.push((i * num[0]))
        }
      }

      let aResultCoincidences = [];
      let bResultCoincidences = [];
      let cResultCoincidences = [];
      let dResultCoincidences = [];

      bResult.forEach(value => {
        aResult.findIndex(item => item === value) > 0 ? bResultCoincidences.push(aResult.findIndex(item => item === value)) : null
      })

      aResult.splice(0, Math.max(...bResultCoincidences) + 1)

      cResult.forEach(value => {
        bResult.findIndex(item => item === value) > 0 ? cResultCoincidences.push(bResult.findIndex(item => item === value)) : null
      })

      bResult.splice(0, Math.max(...cResultCoincidences) + 1)

      dResult.forEach(value => {
        cResult.findIndex(item => item === value) > 0 ? dResultCoincidences.push(cResult.findIndex(item => item === value)) : null
      })

      cResult.splice(0, Math.max(...dResultCoincidences) + 1)

      this.package1 = aResult.length
      this.package2 = bResult.length
      this.package3 = cResult.length
      this.package4 = dResult.length

    },

What happens in my approach is that I try to get all possible results from each multiplication, and then I remove the ones that matches between the arrays I made with this combination, to finally get the result, but this is not well optimized, and I'm sure there is probably a better solution to this problem.

Anyway ignore the vuejs implementation, that's only to set the values in the DOM.

***ES6 solution would be awesome.

CodeSandbox to play around: CODESANDBOX LINK

Thanks in advance.



from Finding the best possible subset combinations of numbers to reach a given sum or closest to it

No comments:

Post a Comment