Javascript/Typescript: Check if Combination of cost and value exists

Question

If i have a list of choices that each have a cost and a value, how can i check if a combination of choices exists, where a given value is exactly met, but a max cost is not overceeded?

Here is an example:

const VAL      = 10;
const MAX_COST = 19;

let choices = [
    [{cost: 10, val: 3}, {cost:8, val: 2}, {cost: 6, val:  1}], // From every line, only one can be chosen
    [{cost: 10, val: 3}, {cost:4, val: 3}, {cost: 6, val:  3}],
    [{cost: 7, val: 5}, {cost:4, val: 3}, {cost: 11, val:  3}],
    [{cost:4, val: 3}, {cost: 11, val:  3}, {cost: 1, val: 1},],
];

In this example the anwser would be yes, because {cost: 10, val: 3}, {cost:4, val: 3}, {cost:4, val: 3}, {cost: 1, val: 1} can be chosen, adding up to a total cost of 19 and having a combined value of exactly 10.

In the real usecase there will be up to 3000 choices that have to be made, so bruteforcing is not viable.

Sorry for my bad English.

Answer 1

Processing 3000 entries isn't a lot of work for JavaScript. Checkout the following example that generates random values and checks your requirements in real-time.

function getRandomInt(max) {
  return Math.floor(Math.random() * max);
}

function randomBoolean(){
    return Math.random() < 0.5;
}


const choices = [];
const VAL      = 12;
const MAX_COST = 19;

for(let i = 0; i < 3000; i++){
    choices.push([
    {
        cost: getRandomInt(10), 
        val:  randomBoolean() ? 4 : 0
    }, 
    {
        cost: getRandomInt(10), 
      val:  4
    }, 
    {
        cost:  getRandomInt(10), 
      val: 4
    }
  ]);
}

const validChoices = choices.filter(options => {
  const totalValue = options.reduce((acc, cur) => cur.val + acc, 0);
    const totalCost = options.reduce((acc, cur) => cur.cost + acc, 0);
  
  return totalValue === VAL && totalCost <= MAX_COST; 
});

console.log(`found ${validChoices.length} valid choices`)