动态编程货币变化

本文介绍了动态编程货币变化的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

我有两个函数递归和迭代计算货币变化;在迭代版本中我需要检查钱是否是变化的倍数（货币模数变化为零）：有没有办法在不检查模数的情况下进行迭代？

  public static int MoneyChangeRecur（int m oney，int [] changes）
 {
 int minChange = 0; 
 
 if（money == 0）return 0; 
 int min = int.MaxValue; 
 for（int i = 0; i< changes.Length; i ++）
 {
 
 
 if（money> = changes [i]）
 {
 minChange = MoneyChangeRecur（money  -  changes [i]，changes）; 
 if（minChange + 1< = min）
 {
 min = minChange + 1; 
} 
} 
} 
返回分钟; 
} 
 
 static int IterativeMoneychange（int money）
 {
 int [] ar = new int [money + 1]; 
 int [] change = {6,5,1}; 
 int min = 9999; 
 int index = 0; 
 for（int i = 0; i< money + 1; i ++）
 {
 
 min = 99999; 
 index = 0; 
 bool modSet = false; 
 for（int j = 0; j< change.Length; j ++）
 {
 
 if（i> = change [j]）
 {
 int mod =（i％change [j]）; 
 
 if（mod == 0&& change [j]！= 1）
 {
 if（！modSet）min = 99999; 
 if（（i-change [j]）< min）
 {
 min =（i  -  change [j]）; 
 modSet = true; 
} 
} 
其他
 {
 if（（i  -  change [j]）< min）
 {
 min =（我 - 改变[j]）; 
 modSet = false; 
 
} 
} 
} 
 
 
} 
 if（min！= 99999）// min = 0; 
 ar [i] = ar [min] +1; 
} 
 
 return ar [money]; 
 
}在此处输入代码

解决方案

I have two functions recursive and iterative to calculate money change; in the iterative version I needed to check for if the money is multiple of change (money modulus change is zero): is there a way to do iterative without checking for modulus?

  public static int MoneyChangeRecur(int money, int[] changes)
    {             
        int minChange = 0;

        if (money == 0) return 0;
        int min = int.MaxValue;
        for (int i = 0; i < changes.Length; i++)
        {


            if (money >= changes[i])
            {
               minChange = MoneyChangeRecur(money - changes[i], changes);
              if (minChange + 1 <= min)
                {
                    min = minChange + 1;
                }
            }
        }
        return min;
    }

    static  int IterativeMoneychange(int money)
    {
        int[] ar = new int[money + 1];
        int[] change = { 6, 5, 1 };
        int min = 9999;
        int index = 0;
        for (int i = 0; i < money+1; i++)
        {

            min = 99999;
            index = 0;
            bool modSet = false;
            for (int j= 0; j <change.Length; j++)
            {

                if (i >= change[j])
                {
                   int mod=(i % change[j]);

                    if(mod==0&&change[j]!=1)
                  {
                      if (!modSet) min = 99999;
                     if ((i-change[j] )< min)
                    {
                        min = (i - change[j]);
                        modSet = true;
                    }
                 }
                    else
                    {
                        if ((i - change[j]) < min)
                        {
                            min = (i - change[j]);
                            modSet = false;

                        }
                    }
                }


            }
            if (min != 99999)// min = 0;
            ar[i] = ar[min] +1;
        }

        return ar[money];

    }enter code here

解决方案

这篇关于动态编程货币变化的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！