Si tengo una lista de opciones que tienen un costo y un valor, ¿cómo puedo verificar si existe una combinación de opciones, donde se cumple exactamente un valor dado, pero no se supera un costo máximo?
Aquí hay un ejemplo:
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},], ]; En este ejemplo, la respuesta sería sí, porque {cost: 10, val: 3}, {cost:4, val: 3}, {cost:4, val: 3}, {cost: 1, val: 1} pueden ser elegido, sumando un costo total de 19 y teniendo un valor combinado de exactamente 10 .
En el caso de uso real, habrá hasta 3000 elecciones que se deben hacer, por lo que la fuerza bruta no es viable.
Perdón por mi mal ingles.
Procesar 3000 entradas no es mucho trabajo para JavaScript. Consulte el siguiente ejemplo que genera valores aleatorios y verifica sus requisitos en tiempo real.
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`)