私は次の要件を支払システムでゲームに取り組んでいます特定の値

Question

を支払うために最適な法案の組み合わせを探す：、10,5,4,3：

1-ゲーム内マネー法案であると仮定2,1

2 AIは正確な金額をカバーするのに必要な最低限の請求書を選択する必要があります。つまり、支払いが必要な場合は8、AIの場合は（4,4,3,3,2）... （3、4、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）を持っています。上記のアルゴリズムを用いて、AIは最適解が（2,2）であるところで（3,2）を選択する。

誰かがこの問題について私に正しい考え方を教えてもらえますか？ありがとう！

Answer 1

ここで私が思いついた再帰的な解決法があります。このアイデアは、「超過」を追跡して、正確に一致するものが見つかるとすぐに戻ることです。完全に一致するものが見つからない場合は、どれだけの請求額が必要なのか、どれだけ多くの請求額を超えて最初のものを取るかによって、超過分を並べ替えるだけです。完全一致で最も少ない請求書を取得するには、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 }))); 

生成されます。この出力

4, 4

4, 4

2, 2

11