优惠券算法问题，求算法帝，来一发！！

Question

问题是这样的：有n个m元的优惠券，要结账y元，求如何最省？？
例如 10元2个， 5元3个 ，3元7个；我分别结账50；28；15元；
发现当数额越小时，算最优解的偏差越多，求算法帝解决一下

//C#

using System;
using System.Collections.Generic;
using System.Linq;

namespace Calculation
{
public class Greedy
{
public string msg = "";
public string Fun(string str)
{
string res = "";
var money = Exchange(Convert.ToDecimal(str));
decimal sum = 0;
foreach (var single in money)
{
if (single.Value != 0)
{
sum += single.Key*single.Value;
string s = string.Format("{0}元---->{1}张; 共{2}元 \r\n", single.Key, single.Value, sum);
res += s;
}
}
return res + "\r\n" + sum + "-" + str + "=" + (sum - Convert.ToDecimal(str)) + "\r\n" + msg;
}
public Dictionary Money = new Dictionary();
public Dictionary SetInit(decimal a,int c)
{
//key表示钱，value表示钱的张数
Money.Add(a, c);
return Money;
}
private Dictionary Exchange(decimal num)
{
//指针
int i = 0;
int count = 1;
Dictionary ResMoney = Money.OrderByDescending(o => o.Key).ToDictionary(o => o.Key, p => p.Value);

        while (true)
        {
            #region 获取当前面值，若指针超出则直接跳出
            decimal tar;
            decimal next;
            if (i > ResMoney.Count)
            {
                //超出
                msg = "i > ResMoney.Count";
                break;
            }
            else
            {
                tar = ResMoney.Keys.ElementAt(i);  //取得面值
            }
            if (i > ResMoney.Count - 2)
            {
                next = 0;
            }
            else
            {
                next = ResMoney.Keys.ElementAt(i + 1);  //取得面值
            }

            #endregion

            if (num > tar)
            {
                num = num - tar;
                //当前面额是否用完
                if (count < ResMoney[tar])
                {
                    count++; //money的张数自增
                }
                else
                {
                    i++; //就去取下一张面值
                    if (i == ResMoney.Count)
                    {
                        msg = "num > tar";
                        break;
                    }
                    ResMoney[tar] = count;
                    count = 1;
                }
            }
            else if (num == tar)
            {
                //当余额等于当前面额时，count跳出  -4 -2 -9 -5
                ResMoney[tar] = count;
                msg = "num == tar";
                break;
            }
            else if (next < num && num < tar && next != 0)
            {
                i++; //就去取下一张面额
                if (i == ResMoney.Count)
                {
                    msg = "next < num && num < tar && next != 0";
                    break;
                }
                ResMoney[tar] = 0;
            }
            else if (num == next && next != 0)
            {
                if (tar == next)
                {
                    //余额等于最小面额，count跳出
                    ResMoney[tar] = count;
                    msg = "num == next && next != 0;tar == next";
                    break;
                }
                else
                {
                    i++; //就去取下一张面额
                    if (i == ResMoney.Count)
                    {
                        msg = "num == next && next != 0";
                        break;
                    }
                    ResMoney[tar] = 0;
                }
            }
            else if (num < next && next != 0)
            {
                //余额小于最小面额，跳出 -2 -1
                ResMoney[tar] = count;
                msg = "num < next && next != 0";  
                break;
            }
            else if (next==0)
            {
                //余额小于最小面额，跳出  -2 -7
                ResMoney[tar] = count;
                msg = "next==0";
                break;
            }
        }

        if (i < ResMoney.Count)
        {
            i++;
            for (;i<ResMoney.Count;i++)
            {
                decimal max = ResMoney.Keys.ElementAt(i);  //取得面值
                ResMoney[max] = 0;
            }
            return ResMoney; 
        }
        else
        {
            return ResMoney;
        }

    }
}

}

Answer 1

典型的背包算法，自己google下。http://blog.csdn.net/xiaowei_cqu/article/details/8191808