计算要分配的音符混合

Question

我需要找出一种现金混合算法来从ATM分发钞票.该算法的目标是:

1. 计算纸币组合以向客户分配所需金额.
2. 在这样做的同时,尽可能均匀地尝试清空现金盒,理想情况(但不是强制性的),现金将同时在所有盒中耗尽.

用户希望获得不同数量的现金,例如500美元,1200美元,6000美元等.没有平均值.该算法需要确定哪些音符以及要分配的音符数量.当然,ATM中的盒式磁带可以改变为不同的值/计数.

另一个限制是ATM当时只能提供30个音符,因此如果计算的音符数量超过此限制,算法必须将音符分成一组,同时考虑上述目标(相等的清空).

这是我想出的:

//Represents a typical cash cassette.
class Cassette
{
   public int Denom { get; set; } //Denomination: (USD)50, (USD)100, etc.
   public int Count { get; set; } //Number of notes.
}

//Our cassettes.
List<Cassette> OriginalCashCassettes = new List<Cassette>();
List<Cassette> CloneCashCassettes = new List<Cassette>();

//Populated.
OriginalCashCassettes.Add(new Cassette { Denom = 50, Count = 1000 });
OriginalCashCassettes.Add(new Cassette { Denom = 100, Count = 1000 });
OriginalCashCassettes.Add(new Cassette { Denom = 200, Count = 1000 });

//Pass original cassettes to clone cassettes.
CloneCashCassettes = OriginalCashCassettes;

//Calculate mix for requested amount.
CalculateNoteMix(6000);

而计算本身:

private void CalculateNoteMix(int reqAmount)
{
    //1. Check if the amount is higher than combined counts.
    int totalCounts = 0;
    foreach (var item in CloneCashCassettes)
    {
        totalCounts += item.Denom * item.Count;
    }

    if (totalCounts < reqAmount)
    {
        Console.WriteLine("You're trying too high - maximum amount available is: " + totalCounts);
        return;
    }

    //2. Check if the amount is dispensable with current denoms.
    int lowestDenom = CloneCashCassettes.Min(c => c.Denom);
    if (reqAmount % lowestDenom != 0)
    {
        Console.WriteLine("Unable to dispense amount with current denoms");
        return;
    }

    //3. Calculate note mix to dispense.
    List<Cassette> noteMix = new List<Cassette>();

    do
    {
        //Sort cash cassettes by highest count first.
        CloneCashCassettes = CloneCashCassettes.OrderByDescending(c => c.Count).ToList();

        //Check if highest count denom can cover the amount.
        if (CloneCashCassettes[0].Denom <= reqAmount)
        {

            //Check if this denom already exists in the mix.
            Cassette noteMixCassette = noteMix.Find(n => n.Denom == CloneCashCassettes[0].Denom);
            if (noteMixCassette == null)
            {
                //Add denom to the note mix.
                noteMix.Add(new Cassette { Denom = CloneCashCassettes[0].Denom, Count = 1 });
            }
            else
            {
                //Increase denom count in the note mix.
                noteMixCassette.Count += 1;
            }

            //Reduce denom count in the cash cassette.
            CloneCashCassettes[0].Count -= 1;
            //Reduce the amount by denom.
            reqAmount -= CloneCashCassettes[0].Denom;
        }
        else
        {
            //The amount is smaller than denom => the denom is unusable - remove it.
            CloneCashCassettes.RemoveAt(0);
        }

    //Keep looping until the amount is 0.
    } while (reqAmount > 0);

    //Print resulting note mix.
    Console.WriteLine("For the amount of " + reqAmount + ", our note mix is:");
    foreach (var item in noteMix)
    {
        Console.WriteLine("Denom: " + item.Denom + " x " + "Count: " + item.Count + " = " + item.Denom * item.Count);
    }
}

使用此代码,如果用户要求400美元,则说明组合为:

Denom: 50 x Count: 2 = 100
Denom: 100 x Count: 1 = 100
Denom: 200 x Count: 1 = 200

或者,如果用户要求25,000美元,那么:

Denom: 50 x Count: 72 = 3600
Denom: 100 x Count: 72 = 7200
Denom: 200 x Count: 71 = 14200

问题:

1. 此代码似乎可以正常使用50和更高的denoms.但是,它有一个20的牛仔裤的问题.任何想法如何解决它？

   例:

       OriginalCashCassettes.Add(new Cassette { Denom = 20, Count = 1000 });
       OriginalCashCassettes.Add(new Cassette { Denom = 50, Count = 1000 });
       OriginalCashCassettes.Add(new Cassette { Denom = 100, Count = 1000 });
   

   用户要价200美元,这是可有可无的.我开始减去:200-100-50-20 = 30 - 20 = 10 - >无法分配.

2. 如果金额是可有可无的(检查中为#2),则检查中存在20的denom的相同问题.

   示例:如上配置的磁带,标号为20.用户要求210美元,这应该是可有可无的(100 + 50 + 20 + 20 + 20).

3. 任何想法如何一般地改进这个算法,所以它会更有效/更快？

谢谢.

Answer 1

你遇到的问题基本上就是你的算法将你引导到一个你不能再分配的地方......一个死胡同(即剩下10美元来分配,但你没有那个面额).

我要做的就是产生所有可能的有效分配排列,然后根据诸如"甚至分配账单"等规则选择哪一个是"最佳"或最优的.可能会有一些快捷方式你可以稍后采取,例如排除明显不好的选择,但如果事情确实有效,你会更容易理解"优化"一点!

我从这个例子(http://www.dotnetperls.com/change)开始,这是一个相当基本的算法,用于确定给定硬币和所需金额的可用变化的排列.这与您的基本问题相同.

public static void Main(string[] args)
{
    List<int> notes = new List<int>();
    List<int> amounts = new List<int>() { 50,100,200 };
    Change(notes, amounts, 0, 0, 250);
}

static void Change(List<int> notes, List<int> amounts, int highest, int sum, int goal)
{
    //
    // See if we are done.
    //
    if (sum == goal)
    {
        Display(notes, amounts);
        return;
    }
    //
    // See if we have too much.
    //
    if (sum > goal)
    {
        return;
    }
    //
    // Loop through amounts.
    //
    foreach (int value in amounts)
    {
        //
        // Only add higher or equal amounts.
        //
        if (value >= highest)
        {
        List<int> copy = new List<int>(notes);
        copy.Add(value);
        Change(copy, amounts, value, sum + value, goal);
        }
    }
}

这是一个实例:http://rextester.com/HIJEQC83701

使用50,100和200的组合要求这个代码为$ 250的排列提供以下输出:

50:5
100:0
200:0

50:3
100:1
200:0

50:1
100:2
200:0

50:1
100:0
200:1

从那里,它很容易选择任何一个选项

a)使用最均匀的音符
b)使用一系列音符,使整个音箱处于最平衡的位置.

我会留给你的!