数据结构--贪心算法解决找零钱问题 这里用的是人民币（）
// 实验小结 吴新强于2013年3月20日0:19:08 桂电 2507实验室
// 贪心算法解决找零钱问题 这里用的是人民币（）
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
namespace Greedy_Algorithm
{
class Program
{
static void Main()
{
int origAmount =4568;//单位角 给了100百，需要找63块的算法（假设不存在几分的）
int toChange = origAmount ;
int remainAmount = 0;
int[] coins = new int[9];
// Console.WriteLine("提示：请输入小于100元的值，找零大于100是没意义的！");
MakeChange(origAmount, remainAmount, coins);
Console.WriteLine();
Console.WriteLine("最优找零方法如下：" + toChange + "角");
Console.WriteLine();
//origAmount = Convert.ToDouble(Console.ReadLine());
Console.WriteLine("找零的人民币是: ");
Console.WriteLine();
ShowChange(coins);
}
static void MakeChange(double origAmount, double remainAmount, int[] coins)
{
if ((origAmount % 500) < origAmount)
{
coins[8] = (int)(origAmount / 500);
remainAmount = origAmount % 500;
origAmount = remainAmount;
}
if ((origAmount % 200) < origAmount)
{
coins[7] = (int)(origAmount / 200);
remainAmount = origAmount % 200;
origAmount = remainAmount;
}
if ((origAmount % 100) < origAmount)
{
coins[6] = (int)(origAmount / 100);
remainAmount = origAmount % 100;
origAmount = remainAmount;
}
if ((origAmount % 50) < origAmount)
{
coins[5] = (int)(origAmount / 50);
remainAmount = origAmount % 50;
origAmount = remainAmount;
}
if ((origAmount % 20) < origAmount)
{
coins[4] = (int)(origAmount / 20);
remainAmount = origAmount % 20;
origAmount = remainAmount;
}
if ((origAmount % 10) < origAmount)
{
coins[3] = (int)(origAmount / 10);
remainAmount = origAmount % 10;
origAmount = remainAmount;
}
if ((origAmount % 5) < origAmount)
{
coins[2] = (int)(origAmount / 5);
remainAmount = origAmount % 5;
origAmount = remainAmount;
}
if ((origAmount % 2) < origAmount)
{
coins[1] = (int)(origAmount / 2);
remainAmount = origAmount % 2;
origAmount = remainAmount;
}
if ((origAmount % 1) < origAmount)
{
coins[0] = (int)(origAmount / 1);
remainAmount = origAmount % 1;
// origAmount = remainAmount;
}
}
static void ShowChange(int[] arr)
{
if (arr[8] > 0)
Console.WriteLine("50元的人民币: " + arr[8] + "张 ");
if (arr[7] > 0)
Console.WriteLine("20元的人民币: " + arr[7] + "张");
if (arr[6] > 0)
Console.WriteLine("10元的人民币: " + arr[6] + "张");
if (arr[5] > 0)
Console.WriteLine("5元的人民币: " + arr[5] + "张");
if (arr[4] > 0)
Console.WriteLine("2元的人民币: " + arr[4] + "张");
if (arr[3] > 0)
Console.WriteLine("1元的人民币: " + arr[3] + "张");
if (arr[2] > 0)
Console.WriteLine("5角的人民币: " + arr[2] + "张");
if (arr[1] > 0)
Console.WriteLine("2角的人民币: " + arr[1] + "张");
if (arr[0] > 0)
Console.WriteLine("1角的人民币: " + arr[0] + "张");
}
}
}
}
实验截图：
