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

first off yes, homework assignment, i've been struggling 3 days, , can't figure out.

basically problem take decimal amount entered user in text box, need take number , break down currency denominations, $50, $20, $10, $5, $1 , if amount has decimal $.25, $.10, $.05, $.01.

and need break down in lowest amount of denominations possible, example $100 broken down 2 $50 bills.

here have far.

private void btndispense_click(object sender, eventargs e) {

        decimal 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 amount of bills         (numberofbills[0] = 0; totalamount >= 50; numberofbills[0]++)         {             totalamount = totalamount - 50;         }         (numberofbills[1] = 0; totalamount < 20; numberofbills[1]++)         {             totalamount = totalamount - 20;         }         (numberofbills[2] = 0; totalamount < 10; numberofbills[2]++)         {             totalamount = totalamount - 10;         }         (numberofbills[3] = 0; totalamount < 5; numberofbills[3]++)         {             totalamount = totalamount - 5;         }         (numberofbills[4] = 0; totalamount <= 0; numberofbills[4]++)         {             totalamount = totalamount - 1;         }           //for loop amount of coins         (numberofcoins[0] = 0; totalamount >= .25m; numberofbills[0]++)         {             totalamount = totalamount - .25m;         }         (numberofbills[1] = 0; totalamount < .10m; numberofbills[1]++)         {             totalamount = totalamount - .10m;         }         (numberofbills[2] = 0; totalamount < .05m; numberofbills[2]++)         {             totalamount = totalamount - .05m;         }         (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 appreciated.

this famous knapsack type problem.you might want start exploring here : https://en.wikipedia.org/wiki/change-making_problem

the best way address problem find possible combinations of change , find optimal solution. below code karamana found on codeproject.com :

//find 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 answer hence quit loop              answer.allpossiblechanges.add(tempsoln);              break;             }              else {             // target not reached, try solution recursively             // current denomination start point.              findallcombinationsrecursive(tempsoln, i, temp, answer);             }          }      } 

in order find optimum solution :

public coinchangeanswer findoptimalchange(int target, int[] denoms) {  coinchangeanswer soln = new coinchangeanswer(target,denoms);  stringbuilder sb = new stringbuilder();   // initialize 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 following more details on explanation  // of 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 original code here