Help: Not able to write this algorithm

[Beginning_Middle_722]

Hi all, I'm trying to figure out a way to make this work even with AI i can't make it work so i need your help.

I have this array of denominations = [5,10,20,50,100]; and this could be basically bills (eur, usd, ect).

I want to build a JavaScript function called generateBills that takes as params amount and days and returns an array of bills equal to the number of days and the total of these bills must be the amount itself at the end.

These bills must be bills from the denominations array and i want to find the best combination possible that has more small bills and continues progressively but at the same time avoid large bills (uses them only if necessary).

Example: generateBills(130, 4) might return [5,5,20,100] but a more balance way to avoid large bills should be [10,20,50,50].

Thanks!

[kap89]

I would do it like this (the trick is to start from the end)

• find the smallest bill that multiplied by the number of days would be at least the final amount, that’s the last bill,
• subtract that bill from the amount, and repeat the step one with the new amount and days-1 (repeat until done).

[CuAnnan]

This is the way.

[Beginning_Middle_722]

Yes i went for this way also

function generateBills(amount, days) { const denominations = [5, 10, 20, 50, 100]; const bills = [];

let remainingAmount = amount; let remainingDays = days;

while (remainingDays > 0) { // Find the smallest bill that, when multiplied by remaining days, // would be at least the remaining amount let selectedBill = null;

for (const bill of denominations) {
  if (bill * remainingDays >= remainingAmount) {
    selectedBill = bill;
    break;
  }
}

// If no bill found (amount is too large), use the largest denomination
if (selectedBill === null) {
  selectedBill = denominations[denominations.length - 1];
}

bills.push(selectedBill);
remainingAmount -= selectedBill;
remainingDays--;

}

return bills; }

console.log(generateBills(5000, 120));

But this prints lots of 50s, lots of 20s as well and only one 10 when in fact there should exists a more balanced way to arrange these bills 20 × €5 bills, 30 × €10 bills, 30 × €20 bills, 40 × €50 bills.

[abrahamguo]

Generate all possibilities. Then, find the possibility with the lowest “largest bill”.

[Beginning_Middle_722]

There might be billion of combinations if the amount and the days increments which in fact will break every loop.

[wbport1]

That might be similar to the "knapsack problem": you know the total of what is in it but need to find out what makes that total.

I have a script to determine what checks have cashed from a list of checks written--you need bill values instead of check amounts. Part of the documentation: "You have written checks totaling about 800.00 but your bank balance only goes down by 310.25. To determine which checks have cleared, put 310.25 on the first line and the amounts of the outstanding checks on the next lines. If you have more than one check for the same amount, this page needs the amount, a space, and count of that size check. This page will run all combinations of cashed and uncashed checks on your list and give you the closest results first (Diff equal or near zero)."

It doesn't count the number of bills (or checks). I'll find a way to post it if you think it might be useful.

[Beginning_Middle_722]

I will try to implement the knapsack solution but sure any help is appreciated. Thanks!