Find the least number of bills required to pay for a certain amount

Unity Engine
1

Hello guys,

I am working on a game and I need a payment algorithm for the following scenario:

1- Suppose the money bills in the game are: 10,5,4,3,2,1

2- AI needs to choose the least number of bills needed to cover the exact amount,i.e if the required to pay is 8 and AI has (4,4,3,3,2)…He can choose (4,4) but not (3,3,2)

3- In case AI can’t make the exact amount using the bills he has, he should choose the combination such that it gives the amount with the least difference value, i.e. if the required amount to pay is 7 and the AI has the following bills ( 10,5,4,4), he choses (4,4) which gives the player 1 more above the needed amount.

I am stuck in implementing this in C#. Any ideas on how to solve this problem?

Thank you!⁠

2

shouts “recursive” to me… write a function that takes in the target value and works out the largest “bill” it can fit into that amount, have the bill as the return value of the function or add it to a list outside the function (or however you’re storing the “bills” it’s picked). Take the selected bill amount away from the target amount and call the same function again (from within the current function call) passing in the new amount.

1 Like
3

I tried this method already, there are some cases it donesnt work with…Suppose your bills are ( 3,2,2) and you need to pay 4…AI will choose (3,2) not (2,2)

4

That’s my code

//sortedValues is a list containing my bills in descending order

//ChosenCardsToPay is a list for the bills I choose to pay with
public void PreparePayment(int neededAmount)
 {

      int remainingAmount = neededAmount;

      int chosenAmount;

      while (remainingAmount > 0) 
      {
          chosenAmount = 0;

          foreach (int moneyValue in sortedValues ) 
          {
              if (moneyValue <= remainingAmount) 
              { 
                  chosenCardsToPay.Add (moneyValue); //AddBillValuetomycandidate list
                  remainingAmount = remainingAmount - moneyValue;
                  chosenAmount = moneyValue;
                  break;
              } 
          }
          if (chosenAmount != 0)
          sortedValues.Remove (moneyValue);//RemoveChosenBillfromInitial List
          else //If all bill values are greater thanremainingamount,ichoosethebillwithsmallestvalueandaddtothecandidate list
          {
              chosenAmount = sortedValues.Last();
              sortedValues.Remove(chosenAmount); chosenCardsToPay.Add (chosenAmount);
              remainingAmount = remainingAmount - moneyValue;
          }
      }
 }
5

This problem has two parts:

1: figure out if you can pay the sum exactly

2: if 1 doesn’t work, select the minimum overshoot.

A recursive function would work, though in the worst-case scenario, you’d end up checking every possible combination of notes. The recursive implementation is pretty simple;

  • remove one note from your set of notes, and check if it’s equal to your sum.
  • If it’s equal, you’ve found the correct set of notes
  • If it’s less than the sum, check if the remaining notes can sum to (sum - note)
  • If it’s greater than the sum, check if it’s the least overshoot, and return to the previous level of recursion.

Making recursive algorithms like this is always a bit of a pain - you’re going to have to send some Lists around, and add/remove from them a bunch. You’re probably going to need a subset function that gives you a list, minus an element.

By the way, 1) is NP complete - it’s* the Subset Sum problem. This means that if you find a polynomial time solution to the problem, or prove that there’s no polynomial time solution, you’ll have solved the hardest problem in computer science!

1 Like
6

Hi,

Well sorry I really didnt follow…is this problem that hard?