# 一道算法面试题目——变种的零钱问题

        /// <summary>
/// 栈解决  多项式量级，考虑优化
/// </summary>
/// <param name="bankValue">当前循环的数字</param>
/// <param name="duePayment">整个数字列表</param>
void calcByStack(int bankValue, List<int> duePayment)
{
DateTime dtbegin = DateTime.Now;
//倒叙排列可以快速得到值 但是数字越小越难计算
duePayment = duePayment.OrderByDescending(o => o).ToList();
//duePayment = duePayment.OrderBy(o => o).ToList();
int count = duePayment.Count();
Stack<int> result = new Stack<int>();
int temp = 0;
for (int i = 0; i < count; i++)
{
temp++;
//排除单数字大于结果的数字
if (duePayment[i] > bankValue)
{
continue;
}
//栈加入
result.Push(duePayment[i]);
//获取当前栈
int nowSum = result.Sum();
if (nowSum > bankValue)
{
result.Pop();
}
else if (nowSum == bankValue)
{
int times = (DateTime.Now - dtbegin).Milliseconds;
dtbegin = DateTime.Now;
drawLbItems(times, 1, result,null);
result.Pop();
}

if (i == count - 1)
{
if (nowSum < bankValue)
{
result.Pop();
}
if (result.Count() > 0)
{
i = duePayment.IndexOf(result.Peek());
result.Pop();
}

}
}
}    

2<3，在往上加。

。。。

。。。

 1 void bw_DoWork(object sender, DoWorkEventArgs e)
2         {
3             //筛掉比总值大的数据，去除重复数据,倒叙排列
4             duePayments = duePayments.Where(o=>o< bankValue).Distinct().OrderByDescending(o => o).ToList();
5             int count = duePayments.Count();
6             result = new List<int>();
7             for (int j = 0; j < count; j++)
8             {
9                 //以每个数字为主计算
11                 calcPruning(bankValue, duePayments, j);
12                 //计算完毕初始化结果
13                 result = new List<int>();
14             }
15         }

 1 /// <summary>
2         /// 剪枝操作跳转，减少大量无需计算的数字
3         /// </summary>
4         /// <param name="bankValue">总值</param>
5         /// <param name="duePayment">全部数据</param>
6         /// <param name="j">当前数字</param>
7         void calcPruning(int bankValue, List<int> duePayment, int j)
8         {
9             //全部数据的最大长度
10             int count = duePayment.Count;
11             for (int i = j + 1; i < count; i++)
12             {
13                 //汇总 获取当前计算值中的数据总值
14                 int nowReuslt = result.Sum();
15                 //差值=总值-当前数据总值
16                 int temp = bankValue - nowReuslt;
17                 //如果差值比当前需要计算的数字大，则直接加入计算
18                 if (temp > duePayment[i])
19                 {
20                     //获取所有小于当前数值的数进行汇总，如果总值小于差值，则向上回溯
21                     var max = duePayment.Where(o => o < duePayment[i]);
22                     if (max.Sum() < temp)
23                     {
25                         //直接回溯
26                         i = count - 1;
27                     }
28                     //否则继续计算
29                     else
30                     {
32                     }
33
34
35                 }
36                 //如果差值等于当前的数字，找到一个正确解
37                 else if (temp == duePayment[i])
38                 {
40                     drawLbItemsBack drawItem = drawLbItems;
41                     lbResult.Invoke(drawItem, (DateTime.Now - beginTime).Milliseconds, 3, null,result);
42                     break;
43                 }
44                 //如果差值小于了当前数字，则做剪枝操作，向下跳转
45                 else
46                 {
47                     //获取当前数组中小于temp的所有数字
48                     var last = duePayment.Where(o => o <= temp);
49                     if (last.Count() > 0)
50                     {
51                         //获取最接近temp的数组下标
52                         i = duePayment.IndexOf(duePayment.Where(o => o <= temp).OrderByDescending(o => o).First()) - 1;
53                     }
54                     else
55                     {
56                         i = count - 1;
57                     }
58                 }
59                 //如果一个循环周期未找到正确数字，待计算数组向上回溯
60                 if (i == count - 1)
61                 {
62                     if (result.Count > 0) {
63                         i = duePayment.IndexOf(result[result.Count - 1]);
64                         //移除最小值向上
65                         result.RemoveAt(result.Count - 1);
66                     }
67                     //获取当前大数组中当前计算的最小的值，为i指定下标跳过
68
69                     if (i == count - 1&&result.Count>0) {
70                         i = duePayment.IndexOf(result[result.Count - 1]);
71                         //移除最小值再次向上回溯
72                         result.RemoveAt(result.Count - 1);
73                         if (result.Count == 0) {
74                             break;
75                         }
76                     }
77
78                 }
79
80
81             }
82
83         }

3分钟出了结果。

(0)
(0)