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:
| Name | Cost | Limit |
|---|---|---|
| A | 25 | 220 |
| B | 30 | 20 |
| C | 50 | 60 |
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.
Your approach isn't bad. The algorithm can be sped up a bit by
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}`);