ATM program, can't figure out how to break down withdraw amount

Question

First off yes, This is a homework assignment, I've been struggling with it for 3 days, and I can't figure it out.

Basically the problem is to take a decimal amount entered by the user in a text box, I then need to take that number and break it down into currency denominations, $50, $20, $10, $5, $1 and if the amount has a decimal then into $.25, $.10, $.05, $.01.

And I need to break this down in the lowest amount of denominations possible, for example $100 would be broken down into 2 $50 bills.

Here is what I have so far.

private void btnDispense_Click(object sender, EventArgs e)
{
    decimal i;
    i = decimal.Parse(txtAmountReq.Text);
    decimal totalAmount = Convert.ToDecimal(txtAmountReq);

    int[] denomBills = { 50, 20, 10, 5, 1 };
    int[] numberOfBills = new int[5];
    decimal[] denomCoins = { .25m, .10m, .05m, .01m };
    int[] numberOfCoins = new int[4];

    //For loop for amount of bills
    for (numberOfBills[0] = 0; totalAmount >= 50; numberOfBills[0]++)
    {
        totalAmount = totalAmount - 50;
    }
    for (numberOfBills[1] = 0; totalAmount < 20; numberOfBills[1]++)
    {
        totalAmount = totalAmount - 20;
    }
    for (numberOfBills[2] = 0; totalAmount < 10; numberOfBills[2]++)
    {
        totalAmount = totalAmount - 10;
    }
    for (numberOfBills[3] = 0; totalAmount < 5; numberOfBills[3]++)
    {
        totalAmount = totalAmount - 5;
    }
    for (numberOfBills[4] = 0; totalAmount <= 0; numberOfBills[4]++)
    {
        totalAmount = totalAmount - 1;
    }


    //For loop for the amount of coins
    for (numberOfCoins[0] = 0; totalAmount >= .25m; numberOfBills[0]++)
    {
        totalAmount = totalAmount - .25m;
    }
    for (numberOfBills[1] = 0; totalAmount < .10m; numberOfBills[1]++)
    {
        totalAmount = totalAmount - .10m;
    }
    for (numberOfBills[2] = 0; totalAmount < .05m; numberOfBills[2]++)
    {
        totalAmount = totalAmount - .05m;
    }
    for (numberOfBills[3] = 0; totalAmount < .01m; numberOfBills[3]++)
    {
        totalAmount = totalAmount - .01m;
    }

    txt50.Text = Convert.ToString(numberOfBills[0]);
    txt20.Text = Convert.ToString(numberOfBills[1]);
    txt10.Text = Convert.ToString(numberOfBills[2]);
    txt5.Text = Convert.ToString(numberOfBills[3]);
    txt1.Text = Convert.ToString(numberOfBills[4]);

    txtQuarter.Text = Convert.ToString(numberOfCoins[0]);
    txtDime.Text = Convert.ToString(numberOfCoins[1]);
    txtNickel.Text = Convert.ToString(numberOfCoins[2]);
    txtPenny.Text = Convert.ToString(numberOfCoins[3]);
}

Any help would be greatly appreciated.

Answer 1

This is very famous knapsack type problem.You might want to start exploring from here : https://en.wikipedia.org/wiki/Change-making_problem

The best way to address this problem is to find all possible combinations of change and then find the optimal solution. Below is the code by karamana I found on codeproject.com :

//find all the combinations
    private void findAllCombinationsRecursive(String tsoln,
              int startIx,
              int remainingTarget,
            CoinChangeAnswer answer) {
        for(int i=startIx; i<answer.denoms.length ;i++) {
            int temp = remainingTarget - answer.denoms[i];
            String tempSoln = tsoln + "" + answer.denoms[i]+ ",";
            if(temp < 0) {
             break;
            }
            if(temp == 0) {
             // reached the answer hence quit from the loop
             answer.allPossibleChanges.add(tempSoln);
             break;
            } 
            else {
            // target not reached, try the solution recursively with the
            // current denomination as the start point.
             findAllCombinationsRecursive(tempSoln, i, temp, answer);
            }
         }
     }

in order to find optimum solution :

public CoinChangeAnswer findOptimalChange(int target, int[] denoms) {
 CoinChangeAnswer soln = new CoinChangeAnswer(target,denoms);
 StringBuilder sb = new StringBuilder();

 // initialize the solution structure
 for(int i=0; i<soln.OPT[0].length ; i++) {
     soln.OPT[0][i] = i;
     soln.optimalChange[0][i] = sb.toString();
     sb.append(denoms[0]+" ");
 }

 // Read through the following for more details on the explanation
 // of the algorithm.
 // http://condor.depaul.edu/~rjohnson/algorithm/coins.pdf
 for(int i=1 ; i<denoms.length ; i++) {
     for(int j=0; j<target+1 ; j++) {
      int value = j;
      int targetWithPrevDenomiation = soln.OPT[i-1][j];
      int ix = (value) - denoms[i];
      if( ix>=0 && (denoms[i] <= value )) {
          int x2 = denoms[i] + soln.OPT[i][ix];
          if(x2 <= target && (1+soln.OPT[i][ix] < targetWithPrevDenomiation))            {
           String temp = soln.optimalChange[i][ix] + denoms[i] + " ";
           soln.optimalChange[i][j] = temp;
           soln.OPT[i][j] = 1 + soln.OPT[i][ix];
          } else {
           soln.optimalChange[i][j] = soln.optimalChange[i-1][j]+ " ";
           soln.OPT[i][j] = targetWithPrevDenomiation;
          }
      } else {
          soln.optimalChange[i][j] = soln.optimalChange[i-1][j];
          soln.OPT[i][j] = targetWithPrevDenomiation;
      }
    }
 }
 return soln;

}

Link to the original code here