i got a small headache over a problem regarding an efficient way to distribute a fixed amount of points evenly between n items that got different costs and limits. Costs don't increase with each item.

Lets say i got 3 Items:

Further we got fixed Points: 5000. I want to know how many times i can buy each. My curent solution runs a loop and deducts the cost from points until either all limits are reached or points ran out. http://jsfiddle.net/nasc8rfL/

var points = 5000;
var costA = 25;
var costB = 30;
...

var limitA = 220;
...

var maxA = 0;

while (points > 0){
   if (points >= costA && limitA > 0){
     points -=costA;
     limitA -=1;
     maxA  =1;
   };
   if (points >= costB && limitB > 0){
     points -=costB;
     limitB -=1;
     maxB  =1;
   };
   if (points >= costC && limitC > 0){
     points -=costC;
     limitC -=1;
     maxC  =1;
   };
   if((points < costA) and (points < costB) and (points <costC)) break; 
}    

console.log(maxA,maxB,maxC);

Eventually it will not stay at A,B,C but variable number of elements(not more than 20) so i'd loop through each element instead of 3 IFs.

I dont actually have to deduct points i just have to know how many of each item can be bought. I feel like im missing something and there is an easier way to determine the number of each.

I've thought about weighting them based on their limits but my head doesnt want to work with me and im pretty stuck right now.

In addition im a beginner in javascript, so if you guys got some tips to get the shown loop faster or more convinient maybe with something like

function func(arr){
  arr.forEach(x=>{doSomething();})

i would be more than happy.

CodePudding user response：

Your approach isn't bad. The algorithm can be sped up a bit by

• keeping the elements in a list, and not just visiting each during each iteration of your outer loop, but by kicking it out of the list once it hit its limit
• not just buying one of each item per round, but as many as feasible if you'd by equally many of each while staying within budget.

const points = 5000;
const items = [
  {name: "A", cost: 25, limit: 220},
  {name: "B", cost: 30, limit: 60},
  {name: "C", cost: 50, limit: 20},
];
let amounts = Object.fromEntries(items.map(i => [i.name, 0]));
let available = items;
let toSpend = points;
do {
  available = available.filter(i => amounts[i.name] < i.limit && i.cost <= toSpend);
  const maxAmount = Math.max(1, Math.floor(toSpend / available.reduce((s, i) => s i.cost, 0)));
  for (const a of available) {
    const amount = Math.min(maxAmount, a.limit - amounts[a.name]);
    if (amount * a.cost <= toSpend) {
      amounts[a.name]  = amount;
      toSpend -= amount * a.cost;
    } else {
      break;
    }
  }
} while (available.length);
console.log(amounts);
console.log(`Leftover: ${toSpend}`);