获得具有个别成本和限制的最大可负担物品数量的算法

Question

关于在具有不同成本和限制的 n 个项目之间均匀分配固定数量点的有效方法的问题，我有点头疼。每个项目的成本不会增加。

假设我有 3 个项目：

Name	Cost	Limit
A	25	220
B	30	20
C	50	60

此外，我们还获得了固定积分：5000。我想知道我可以购买多少次。我当前的解决方案运行一个循环并从点数中扣除成本，直到达到所有限制或点数运行。 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);

最终它不会停留在 A、B、C，而是可变数量的元素（不超过 20 个）所以我会遍历每个元素而不是 3 个 IF。

我其实不用扣分，我只需要知道每件商品能买多少。我觉得我遗漏了什么，有一种更简单的方法来确定每一个的数量。

我曾考虑过根据它们的极限对它们进行加权，但我的头脑不想和我一起工作，我现在很困。

此外，我是 javascript 的初学者，所以如果你们有一些技巧可以使显示的循环更快或更方便，也许可以使用

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

我会非常高兴。

Answer 1

你的方法不错。该算法可以通过

加快一点

将元素保留在一个列表中，而不只是在外循环的每次迭代中访问每个元素，而是在达到限制后将其踢出列表
不仅每轮每件都买一件，而且如果你在预算范围内每件都买同样多的话，尽可能多买。

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}`);

获得具有个别成本和限制的最大可负担物品数量的算法

Algorithm to get maximum affordable amount of items with individual costs and limits

javascript

algorithm

math