koobas.hobune.stream
Find the least number of bills required to pay for a certain amount
Find the least number of bills required to pay for a certain amount down vote favorite 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?
Here is the code:
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); //Add Bill Value to my candidate list
remainingAmount = remainingAmount - moneyValue;
chosenAmount = moneyValue;
break;
}
}
if (chosenAmount != 0)
sortedValues.Remove (moneyValue);//Remove Chosen Bill from Initial List
else //If all bill values are greater than remaining amount, i choose the bill with smallest value and add to the candidate list
{
chosenAmount = sortedValues.Last();
sortedValues.Remove(chosenAmount); chosenCardsToPay.Add (chosenAmount);
remainingAmount = remainingAmount - moneyValue;
}
}
}
Thank you!
( "Find the least number of bills required to pay for a certain amount down vote favorite" sounds an awful lot like you copied this question from another website? )
The parameters of your problem seem pretty well prescribed. What have you tried? Where did you get stuck?
Probably from SO
Curiously, this is the cached version and clicking the actual Google link takes you here
His question has been marked as a duplicate and has a reference to the other question.
Since SO is actually a more general program$$anonymous$$g Q&A site i don't think this question belongs here on UA as it has nothing to do with Unity. Also the referenced question seems to have answers.
Apart from that case 1 is quite trivial as you just have to keep subtracting the next smaller note as long as the remaining amount is larger or equal to the current note. Case 2 is more complicated as i don't see a way around testing all combinations that cover the target amount and pick the best one. This should be quite easy with a recursive method and a struct that represents the current money state of each "bill type".
