c# - 查找最佳账单组合以支付特定的值(value)

我正在开发游戏支付系统，要求如下：
假设游戏中的钞票是：10,5,4,3,2,1
2-人工智能需要选择支付准确金额所需的最少账单数量，即如果要求支付的账单数量为8，人工智能拥有（4,4,3,3,2）…他可以选择（4,4），但不能选择（3,3,2）
3-如果AI不能使用他拥有的账单来确定确切的金额，他应该选择一个组合，使其给出的金额具有最小的差额值，即如果需要支付的金额是7，并且AI拥有以下账单（10,5,4,4），他选择（4,4），这将使玩家比需要的金额多出1。
下面是我的代码

//sortedValues is a list containing my bills in descending order
//ChosenCardsToPay is a list for the bills I choose to pay with

public void PreparePayment(int neededAmount)
{

    int remainingAmount = neededAmount;

    int chosenAmount;

    while (remainingAmount > 0)
    {
        chosenAmount = 0;

        foreach (int moneyValue in sortedValues )
        {
            if (moneyValue <= remainingAmount)
            {   chosenCardsToPay.Add (moneyValue); //Add Bill Value to my candidate list
                remainingAmount = remainingAmount - moneyValue;
                chosenAmount = moneyValue;
                break;
            }
        }
        if (chosenAmount != 0)
            sortedValues.Remove (moneyValue);//Remove Chosen Bill from Initial List
        else //If all bill values are greater than remaining amount, i choose the bill with smallest value and add to the candidate list
        {
            chosenAmount = sortedValues.Last();
            sortedValues.Remove(chosenAmount);
            chosenCardsToPay.Add (chosenAmount);
            remainingAmount = remainingAmount - moneyValue;
        }
    }
}

大多数情况下，它都能正常工作，但以这种情况为例：所需的金额是4，而ai有（3,2,2）作为账单。利用上述算法，人工智能选择（3，2）的最佳答案是（2，2）。
有人能指点我正确地思考这个问题吗谢谢！

最佳答案

这是我想出的递归解决方案。这样做的目的是跟踪“超龄”的情况，并在找到完全匹配的情况下立即返回。如果找不到完全匹配的，你只需根据超额部分的金额，然后根据需要的账单数量，对超额部分进行排序，然后取第一张为了在完全匹配的情况下获得最少的账单，请确保bills按降序排序。此外，如果无法用给定的一组账单支付金额，则返回空序列。

public static IEnumerable<int> CoverAmount(
    int amount, List<int> bills, HashSet<int> used = null)
{
    if (used == null)
        used = new HashSet<int>();
    if (amount <= 0)
        return Enumerable.Empty<int>();

    var overages = new List<Tuple<List<int>, int>>();
    for(int index = 0; index < bills.Count; index++)
    {
        var bill = bills[index];
        if (used.Contains(index))
            continue;
        if (bill > amount)
        {
            overages.Add(Tuple.Create(new List<int> { bill }, bill - amount));
        }
        else if (bill == amount)
        {
            return Enumerable.Repeat(bill, 1);
        }
        else
        {
            used.Add(index);
            var bestSub = CoverAmount(amount - bill, bills, used).ToList();
            used.Remove(index);
            bestSub.Add(bill);
            var sum = bestSub.Sum();
            if (sum == amount)
            {
                return bestSub;
            }

            if (sum > amount)
            {
                overages.Add(Tuple.Create(bestSub, sum - amount));
            }
        }
    }

    return overages
        .OrderBy(t => t.Item2)
        .ThenBy(t => t.Item1.Count)
        .FirstOrDefault()?.Item1 ?? Enumerable.Empty<int>();

    // OR this if you are not using C# 6
    // var bestOverage = overages
    //    .OrderBy(t => t.Item2)
    //    .ThenBy(t => t.Item1.Count)
    //    .FirstOrDefault();
    // return bestOverage == null ? Enumerable.Empty<int>() : bestOverage.Item1;
}

以下代码

Console.WriteLine(string.Join(", ", CoverAmount(8, new List<int> { 4, 4, 3, 3, 2 })));
Console.WriteLine(string.Join(", ", CoverAmount(7, new List<int> { 10, 5, 4, 4 })));
Console.WriteLine(string.Join(", ", CoverAmount(4, new List<int> { 3, 2, 2 })));
Console.WriteLine(string.Join(", ", CoverAmount(10, new List<int> { 11, 6, 5 })));

将产生此输出
四，四
四，四
2，2个
十一

关于c# - 查找最佳账单组合以支付特定的值(value)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/37326105/