Finden Sie die optimale Kombination Rechnungen für einen bestimmten Wert zu zahlen

Question

ich auf Spiel mit Zahlungssystem, mit folgenden Anforderungen arbeite:

1- die Geldscheine im Spiel Angenommen sind: 10,5,4,3, 2,1

2-AI muss die geringste Anzahl von Rechnungen wählen, die benötigt wird, um den genauen Betrag abzudecken, dh wenn der zu zahlende Betrag 8 ist und AI (4,4,3,3,2) ... Er kann wählen (4,4) aber nicht (3,3,2)

3- Falls AI die genaue Menge nicht mit den Rechnungen, die er hat, eingeben kann, sollte er die Kombination so wählen, dass sie den Betrag angibt mit dem geringsten Differenzwert, dh wenn das erforderlich ist Betrag zu zahlen ist 7 und die KI hat die folgenden Rechnungen (10,5,4,4), er wählt (4,4) was dem Spieler 1 mehr über den benötigten Betrag gibt.

Unten ist mein Code

//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; 
     } 
    } 
} 

Es funktioniert gut, die meisten der Zeit, aber diesen Fall nehmen: Erforderliche Menge ist 4 und AI hat (3,2,2) als Rechnungen. Unter Verwendung des obigen Algorithmus wählt AI (3,2), wo die optimale Antwort (2,2) ist.

Darf mich jemand auf der rechten Seite über dieses Problem nachdenken? Vielen Dank!

Answer 1

Hier ist eine rekursive Lösung, die ich kam. Die Idee ist, "Überschüsse" zu verfolgen und sofort zurückzukehren, wenn Sie eine genaue Übereinstimmung finden. Wenn keine genaue Übereinstimmung gefunden wird, sortieren Sie einfach die Überschüsse nach dem Überlauf, danach, wie viele Rechnungen benötigt wurden und nehmen Sie den ersten. Um die wenigsten Rechnungen für exakte Übereinstimmungen zu erhalten, stellen Sie sicher, dass bills in absteigender Reihenfolge sortiert ist. Auch dies wird eine leere Sequenz zurückgeben, wenn es keine Möglichkeit gibt, den Betrag mit dem gegebenen Satz von Rechnungen zu decken.

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; 
} 

Der folgende Code

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 }))); 

produzieren diese Ausgabe

4, 4

4, 4

2, 2

11