Подсчитайте количество способов сделать сумму с учетом изменений

Question

Я пытался написать алгоритм для подсчета количества различных возможных способов получения определенной суммы с заданными номиналами.Предположим, что доллар США доступен в номиналах 100, 50, 20, 10, 5, 1, 0,25, 0,10, 0,05 и 0,01 долл. США.Приведенная ниже функция прекрасно работает для значений int и int

/* Count number of ways of making different combination */
int Count_Num_Ways(double amt, int numDenom, double S[]){
   cout << amt << endl; //getchar();

  /* combination leads to the amount */
  if(amt == 0.00)
    return 1;

  /* No combination can lead to negative sum*/
  if(amt < 0.00)
    return 0;

  /* All denominations have been exhausted and we have not reached
     the required sum */
  if(numDenom < 0 && amt >= 0.00)
    return 0;

  /* either we pick this denomination, this causes a reduction of 
     picked denomination from the sum for further subproblem, or 
     we choose to not pick this denomination and 
     try a different denomination */
   return Count_Num_Ways(amt, numDenom - 1, S) + 
          Count_Num_Ways(amt - S[numDenom], numDenom, S);
}

, но когда я меняю свою логику с int на float, она входит в бесконечный цикл.Я подозреваю, что это из-за сравнений с плавающей точкой в ​​коде.Я не могу выяснить точную причину бесконечного цикла поведения.Любая помощь в этом отношении будет полезна.

Answer 1

При работе с такими «небольшими» суммами в валюте и без учета процентов будет гораздо проще иметь дело только с центами и целыми суммами, без использования плавающей запятой.

Так что просто измените формулу на использованиеценты, а не доллары и продолжают использовать целые числа.Затем, когда вам нужно отобразить суммы, просто разделите их на 100, чтобы получить доллары, и по модулю 100, чтобы получить центы.

Answer 2

операции с плавающей запятой не могут быть точными из-за конечного представления. Таким образом, вы никогда не будете в конечном итоге с 0,0. Вот почему вы всегда проверяете интервал так:

if (fabs(amt - 0.0) < TOL)

с заданным допуском TOL. TOL выбирается соответствующим образом для применения, в этом случае 1/2 цента уже должно быть в порядке.

РЕДАКТИРОВАТЬ: Конечно, для такого рода вещей Daemin ответ гораздо более подходящим.