CODEWITHSUNDEEP
javascriptalgorithmnumbers
Teiem
Teiem

Reputation: 1629

cover bigger number, with selection of given smaller numbers

I have an array of numbers (e.g. [2, 4, 5, 7]) and have to find the best possible combination to "cover" a bigger number, "cover" meaning here that the sum of the selected numbers should be at least equal to the bigger number. The sum of the selection should be as close as possible to the bigger number and in case of 2+ possible optimal selections, the one which uses fewer numbers in its sum should be chosen, in case there are still 2+ possible options, the one whose chosen numbers come further in front of the array should be returned. A number cant be used twice, unless it appears twice in the given array.
example: 

[2, 4, 5, 7], to cover 10 => [4,7] since 11 is the closest to 10 (and at least 10) possible

[5, 6, 3, 6, 20], to cover 18 => [20], since 20 is the closest to 18 (and at least 18) possible and [20] uses fewer numbers than [5, 6, 3, 6]

My problem is that I have a tree like data structure and want to collapse as few elements as possible, while allowing the user the see as much as possible without scrolling. You dont have to code anything just an Idea for an algorithm would be enough (my implementation would be in js though).

Thank you in advance :)

Upvotes: 1

Views: 108

Answers (2)

Wesley Yang
Wesley Yang

Reputation: 376

You can do it like this:

const arr_origin = [2,4,5,7,2,4,5,20];
const arr_unique = [...new Set(arr_origin)];
const cover_num = 10;

var closest_sum = arr_origin.reduce((a,b) => a+b, 0);
var arr_optimal = arr_unique;

find([], 0);

function find(arr_now, idx) {
    const sum = arr_now.reduce((a,b) => a+b, 0);

    if ( (cover_num <= sum && sum < closest_sum) || 
         (cover_num <= sum && sum == closest_sum && arr_now.length < arr_optimal.length) )
    {
        closest_sum = sum;
        arr_optimal = arr_now;
    }

    if (idx < arr_unique.length) {
        // skip this element
        find(arr_now, idx+1);

        // add this element into array
        var arr_new = arr_now.slice(0);
        arr_new.push(arr_unique[idx]);
        find(arr_new, idx+1);
    }
}

This will gives:

// [2, 4, 5, 7], to cover 10 => [4,7], 11
// [5, 6, 3, 6, 20], to cover 18 => [20], 20
// [2,4,5,7,2,4,5,20], to cover 10 => [4,7], 11

Thanks

Upvotes: 2

Miaplacidus
Miaplacidus

Reputation: 545

With a few initial tests, this solution appears to work:

Repl Example

const maxValue = (array, targetValue) => {
  array.sort((a, b) => (a < b) ? -1 : 1)
  let sums = []
  for(let i = 0; i < array.length - 1; i++) {
    let addends = []
    let addendX = array[i]
    let currentSum = addendX
    let closest = (currentSum >= targetValue)
      ? true
      : false
    addends.push(addendX)
    for(let j = i + 1; j < array.length; j++) {
      if(closest) break
      let addendY = array[j]
      if(
        !closest &&
        currentSum + addendY >= targetValue
      ) {
        currentSum += addendY
        closest = true
      } else {
        currentSum += addendY
      }
      addends.push(addendY)
    }
    sums.push({
      sum: currentSum,
      addends: addends,
    })
  }
  return sums.sort((a, b) => (a.sum < b.sum) ? -1 : 1)[0]
}
console.log(maxValue([2, 4, 5, 7], 11))
/*
{ sum: 11, addends: [ 2, 4, 5 ] }
*/
console.log(maxValue([5, 6, 3, 6, 20], 18))
/*
{ sum: 20, addends: [ 3, 5, 6, 6 ] }
*/

It could probably use some optimization or may produce inaccurate results, but you would have to provide more test cases for me to work through those issues.

Upvotes: 1

Related Questions