Erklärung des Algorithmus:Holen Sie sich die maximalen Artikel, die Sie mit einem festen Budget kaufen können

Erklärung des Algorithmus:Holen Sie sich die maximalen Artikel, die Sie mit einem festen Budget kaufen können

Problemstellung: Bei einem festen Budget und einer Liste mit Artikelpreisen. Was ist die maximale Anzahl an Artikeln, die Sie kaufen können? Sie können jeden Artikel nur einmal kaufen.

Hinweis:Dies ist das Mark-and-Toys-Problem von HackerRank.

Beispiel:

Sie erhalten 10 $ und eine Liste mit Artikeln zur Auswahl:

  • Eine kühle Kaffeetasse für 10 $.
  • Eine Packung Stifte für 2 $.
  • Ein Notizbuch für 8 $.

Sie können maximal 2 Artikel kaufen (die 2-Dollar-Bleistifte und das 8-Dollar-Notizbuch).

Ansatz

Der Brute-Force-Ansatz für dieses Problem besteht darin, alle möglichen Preiskombinationen zu betrachten. Wir haben N Preise. Betrachten Sie zunächst die Summe aller N Preise. Wenn das Budget überschritten wird, sehen Sie sich alle Kombinationen mit N – 1 Preisen an. Usw. Im schlimmsten Fall würden wir 2^N – 1 Preiskombinationen betrachten, was bedeutet, dass die Zeitkomplexität O(2^N) ist. Schlimmer kann es kaum werden.

Hinweis:2^N – 1 =(N wähle 1) + (N wähle 2) + … + (N wähle N).

Werde gierig

Wir müssen nicht alle Preiskombinationen betrachten. Stattdessen können wir einen Greedy-Algorithmus-Ansatz verwenden. Wenn wir einen Artikel kaufen, ist er nicht mehr verfügbar und wir ziehen ihn vom Budget ab. Um die Anzahl der gekauften Artikel zu maximieren, kaufen wir so lange den billigsten verfügbaren Artikel, bis das Budget aufgebraucht ist (oder wenn keine Artikel mehr verfügbar sind).

Hier ist ein Schritt-für-Schritt-Beispiel für die Ausführung dieses Algorithmus:

budget = 10
prices = [10, 2, 8]

iteration 1
   2 is the lowest price in [10, 2, 8]
   subtract 2 from budget, leaving 8 remaining
   remove 2 from available prices
   
iteration 2
   8 is the lowest price in [10, 8]
   subtract 8 from budget, leaving 0 remaining

There's no budget remaining, so return the number of items purchased.Code language: plaintext (plaintext)

Wie suchen wir in jeder Iteration nach dem niedrigsten Preis? Da wir es mit einer ungeordneten Liste zu tun haben, müssen wir die Liste der verfügbaren Preise durchlaufen, um sie zu finden. Da wir N Elemente haben, durchlaufen wir jedes Element N-mal, was zu einer Zeitkomplexität von O(n^2) führt. Dies ist weitaus besser als der Brute-Force-O(2^N)-Ansatz.

Hinweis:Artikel können nicht teilweise gekauft werden. Ihr Preis muss vollständig durch das verbleibende Budget gedeckt werden. Wenn Sie beispielsweise 5 $ übrig haben, können Sie keinen 10 $-Artikel kaufen. Dies ist ein Grenzfall zum Testen.

Optimieren durch Sortieren

Anstatt bei jeder Iteration nach dem niedrigsten Preis zu suchen, können wir optimieren, indem wir die Anfangspreise in aufsteigender Reihenfolge sortieren. Wir verwenden eine integrierte Sortierfunktion.

Das bedeutet, wenn wir die Preise durchgehen, haben wir es immer mit dem niedrigsten verfügbaren Preis zu tun. Wenn wir einen Artikel nicht kaufen können, wissen wir, dass wir auch keinen der verbleibenden Artikel kaufen können, also können wir vorzeitig aussteigen.

Das Sortieren hat im ungünstigsten Fall eine Zeitkomplexität von O(N log N). Nach dem Sortieren müssen wir einfach die Preise durchgehen, bis das Budget aufgebraucht ist. Das bedeutet, dass wir die Elemente nur einmal durchlaufen müssen – eine Zeitkomplexität von O(N).

Am Ende hat unser Algorithmus nun eine Zeitkomplexität von O(N log N) (man behält nur den höchsten Term in Big-O). Dies ist eine Verbesserung um eine Größenordnung gegenüber dem nicht optimierten O(n^2)-Ansatz.

Das Sortieren verbessert nicht nur die Leistung, sondern vereinfacht auch die Logik (weil wir die Artikelverfügbarkeit nicht mehr explizit verwalten müssen). Sortieren kann so verwendet werden, um Probleme zu vereinfachen.

Code

Jetzt können wir den oben besprochenen Ansatz des optimierten Greedy-Algorithmus implementieren.

Algorithmus

Hier ist der Code.

public static int CalcMaxPurchasedItems(int budget, int[] itemPrices)
{
	int itemsPurchased = 0;

	Array.Sort(itemPrices);

	foreach(var itemPrice in itemPrices)
	{
		budget -= itemPrice;

		if (budget < 0)
			break;

		itemsPurchased++;
	}

	return itemsPurchased;
}
Code language: C# (cs)

Dies verwendet Array.Sort(), um die anfängliche Preisliste zu sortieren. Theoretisch hat dies eine zeitliche Komplexität von O(N log N). In Wirklichkeit ist es viel schneller als das, weil es Optimierungen für Integer-Arrays hat.

Tests

Hier sind die Komponententests, die die besprochenen Testszenarien abdecken:

[TestMethod()]
public void Test1Item_WhenBudgetLessThanItemPrice_Returns0()
{
	//arrange
	var budget = 10;
	var itemPrices = new int[] { 20 };

	//act
	var maxItemsPurchased = Algorithm.CalcMaxPurchasedItems(budget, itemPrices);

	//assert
	Assert.AreEqual(0, maxItemsPurchased);
}
[TestMethod()]
public void Test1Item_WhenBudgetGreaterThanOrEqualToItemPrice_Returns1()
{
	//arrange
	var budget = 10;
	var itemPrices = new int[] { 5 };

	//act
	var maxItemsPurchased = Algorithm.CalcMaxPurchasedItems(budget, itemPrices);

	//assert
	Assert.AreEqual(1, maxItemsPurchased);
}
[TestMethod()]
public void Test_OnlyCountsItemIfItCanBeFullyPurchased()
{
	//arrange
	var budget = 10;
	var itemPrices = new int[] { 5, 6 };

	//act
	var maxItemsPurchased = Algorithm.CalcMaxPurchasedItems(budget, itemPrices);

	//assert
	Assert.AreEqual(1, maxItemsPurchased);
}
[TestMethod()]
public void Test_WhenMultipleValidCombos_ChoosesTheMax()
{
	//arrange
	var budget = 10;
	var itemPrices = new int[] { 2, 3, 5, 5 };

	//act
	var maxItemsPurchased = Algorithm.CalcMaxPurchasedItems(budget, itemPrices);

	//assert
	Assert.AreEqual(3, maxItemsPurchased);
}
Code language: C# (cs)