PHP - Finde minimalen Wert in einem Array und kombiniere alle möglichen Zahlen, um eine bestimmte Summe zu erreichen

Question

Nicht sicher folgendes Szenario gehört zu Knapsack Problem oder Coin Change Approach. Möchte eine Lösung dieses Problems in PHP Sprache suchen. Erfordern einfache Lösung, weil einige Algorithmen (Texttheorie) aus dem Internet nicht verstehen.

Bei einer Tabelle (A), wie folgend:

TABLE (A) 
--------- 
Item | Name | Price ($) 
-------- ------------ -------------- 
1  | Adidas |  35 
2  | Nike Run |  70 
3  | Puma  |  100 
4  | Nike  |  85 
5  | NB  |  65 

1. alle 3 Elemente in der Tabelle (A) Kombinieren, summieren mehr als oder gleich 200 $.
   • Zuerst sortieren Sie die Tabelle (A).
   • Zweitens, erhalten Sie die minimale/kleinste Menge (Preis). In diesem Fall ist $ 35.
   • Drittens, überprüfen Sie eins nach dem anderen von den anderen Betrag.
   • Viertens, summieren Sie 3 Kombinationsmöglichkeiten, die mehr als oder gleich $ 200 sind.

Ergebnis:

Item | Name | Price ($) 
-------- ------------ -------------- 
1  | Adidas |  35 
5  | NB  |  65 
3  | Puma  |  100 

weitere Probe Tabelle (B), wie folgend:

TABLE (B) 
--------- 
Item | Name | Price ($) 
-------- ------------ -------------- 
1  | Adidas |  5 
2  | Nike Run |  35 
3  | Puma  |  110 
4  | Nike  |  65 
5  | NB  |  15 

1. in der Tabelle alle 3 Einzelteile kombinieren (B), sum mehr als oder gleich $ 200.
   • Zuerst sortieren Sie die Tabelle (B).
   • Zweitens, erhalten Sie die minimale/kleinste Menge (Preis). In diesem Fall ist $ 5.
   • Drittens, überprüfen Sie eins nach dem anderen von den anderen Betrag.
   • Viertens, summieren Sie 3 Kombinationsmöglichkeiten, die mehr als oder gleich $ 200 sind.
   • Fünftens, wenn die kleinsten mit anderen kombinieren und insgesamt $ 200 summieren, erhalten Sie die zweitkleinste und wiederholen Sie den ersten bis vierten Schritt.
   • Sechstens, der beste minimale/kleinste Wert ist $ 35 in diesem Fall.

Ergebnis:

Item | Name | Price ($) 
-------- ------------ -------------- 
2  | Nike Run |  35 
4  | Nike  |  65 
3  | Puma  |  110 

Answer 1

Say Tabelle A ist ein assoziatives Array, nennen wir es ein $. Um die erste Kombination zu finden, die> = 200 dies tun wird:

$rowsWithValueOver200 = array(); 
foreach($a as $value) { 
    foreach($a as $value2) { 
     // Make sure to ignore the value selected in the first loop. 
     if ($value2 == $value) 
      continue; 

     foreach($a as $value3) { 
      // Make sure to ignore the value selected in the first and second loop. 
      if ($value3 == $value) 
       continue; 
      if ($value3 == $value2) 
       continue; 

      $total = $value3['Price'] + $value2['Price'] + $value['Price']; 

      if ($total >= 200) { 
       // Store all of the rows in the new array. 
       $rowsWithValueOver200[] = $value; 
       $rowsWithValueOver200[] = $value2; 
       $rowsWithValueOver200[] = $value3; 
       break; 
      } 
     } 
    } 
} 

So wir 3-mal durch das Array iterieren. Überprüfen Sie die Summe, sobald wir 3 eindeutige Werte betrachten. Die ganze Zeit stellen Sie sicher, dass wir das zuvor ausgewählte Array-Element ($ value oder $ value2) nicht einschließen. Dies könnte sicherlich etwas aufgeräumt und universeller gemacht werden, aber es wird für 3 Elemente funktionieren. Ein Refactor davon in eine universellere Funktion würde rekursive Aufrufe an sich selbst machen, eine Startposition zulassen (dann eine for-Schleife anstelle von foreach verwenden).

Den minimalen Wert zu finden ist ziemlich einfach.

$minVal = PHP_INT_MAX; // Initially something high, here it is the maximum integer value. 
$minRow; 
foreach($rowsWithValueOver200 as $value) { 
    if ($value['Price'] < $minVal){ 
     $minVal = $value['Price']; 
     $minRow = $value; 
    } 
} 

Stellen Sie Ihren Minimalwert (MINVAL) gegen etwas zu überprüfen, wirklich hoch. Iterate durch die Array-Werte und wenn der $ value ['Price'] kleiner ist als die aktuelle minVal, dann ist es jetzt die minVal und speichert das Array-Element in $ minRow für spätere Referenz.

3 und 4 Ich bin mir nicht sicher, was Sie fragen. Es ist nicht klar. Wenn Sie die Summe der drei Zeilen in $ rowsWithValueOver200 finden möchten, können Sie einfach das verwenden, was ich in der ersten Antwort hatte. Wenn Sie es nur mit den drei letzten Elemente tun wollen, dann tun:

$total = 0; 
foreach($rowsWithValueOver200 as $value) { 
    $total += $value['Price']; 
} 

Wenn Sie nach anderen Möglichkeiten suchen, die nur bis 200 oder mehr summieren dann das erste Beispiel verwenden, aber anstelle eines foreach Verwenden Sie in der ersten Schleife eine for-Schleife mit einem Index. Beginnen Sie bei jedem Index.

Viel Glück!

Answer 2

MySQL ist richtig ausgestattet, um das alles alleine zu erreichen. Sie könnte ziehen Sie Ihre gesamte Tabelle für PHP, um herauszufinden, aber dies kann auf Ressourcen teuer werden, und es wird auf jeden Fall langsamere Ergebnisse, insbesondere mit größeren Datenbanken produzieren. PHP muss normalerweise die Daten mehrere Male durchschleifen, um genügend Array-Manipulationen durchzuführen, die MySQL sehr einfach durchführen kann.

Angenommen, Ihre Datenbank sieht wie folgt aus:

CREATE TABLE IF NOT EXISTS `A` (
    `Item` int(10) unsigned NOT NULL AUTO_INCREMENT, 
    `Name` varchar(10) NOT NULL, 
    `Price` decimal(10,2) NOT NULL, 
    PRIMARY KEY (`Item`), 
    UNIQUE KEY `Name` (`Name`) 
) ENGINE=InnoDB DEFAULT CHARSET=latin1 AUTO_INCREMENT=6 ; 

INSERT INTO `A` (`Item`, `Name`, `Price`) VALUES 
(1, 'Adidas', '35.00'), 
(2, 'Nike Run', '70.00'), 
(3, 'Puma', '100.00'), 
(4, 'Nike', '85.00'), 
(5, 'NB', '65.00'); 

Sie können abfragen, wie so:

SELECT @leastprice := min(`Price`) FROM `A`; 
SELECT t1.Name AS Name1, t2.Name AS Name2, t3.Name AS Name3, 
     t1.Price AS Price1, t2.Price AS Price2, t3.Price AS Price3, 
     (t1.Price+t2.Price+t3.Price) AS `Total` 
    FROM `A` t1 
    LEFT JOIN `A` t2 ON t1.Item != t2.Item 
    LEFT JOIN `A` t3 ON t1.Item != t2.Item AND t2.Item != t3.Item 
    WHERE t1.price = @leastprice 
     AND t2.price<=t3.price 
     AND t1.price+t2.price+t3.price >= 200; 

Ergebnis:

---

Edit:
Für Ihren zweiten Fall sieht wie folgt aus Ihrer Datenbank unter der Annahme:

SELECT @leastTalliablePrice := min(t1.Price) FROM `B` t1 
    LEFT JOIN `B` t2 ON t1.Item != t2.Item 
    LEFT JOIN `B` t3 ON t1.Item != t2.Item AND t2.Item != t3.Item 
    WHERE t2.price<=t3.price 
     AND t1.price+t2.price+t3.price >= 200; 
SELECT t1.Name AS Name1, t2.Name AS Name2, t3.Name AS Name3, 
     t1.Price AS Price1, t2.Price AS Price2, t3.Price AS Price3, 
     (t1.Price+t2.Price+t3.Price) AS `Total` 
    FROM `B` t1 
    LEFT JOIN `B` t2 ON t1.Item != t2.Item 
    LEFT JOIN `B` t3 ON t1.Item != t2.Item AND t2.Item != t3.Item 
    WHERE t1.price = @leastTalliablePrice 
     AND t2.price <= t3.price 
     AND t1.price+t2.price+t3.price >= 200; 

Ergebnis:

Wenn für einige

CREATE TABLE IF NOT EXISTS `B` (
    `Item` int(10) unsigned NOT NULL AUTO_INCREMENT, 
    `Name` varchar(10) NOT NULL, 
    `Price` decimal(10,2) NOT NULL, 
    PRIMARY KEY (`Item`), 
    UNIQUE KEY `Name` (`Name`) 
) ENGINE=InnoDB DEFAULT CHARSET=latin1 AUTO_INCREMENT=6 ; 

INSERT INTO `B` (`Item`, `Name`, `Price`) VALUES 
(1, 'Adidas', '5.00'), 
(2, 'Nike Run', '35.00'), 
(3, 'Puma', '110.00'), 
(4, 'Nike', '65.00'), 
(5, 'NB', '15.00'); 

Sie es wie so abfragen Aus diesem Grund hat Ihre Datenbank nicht 3 oder mehr verschiedene Artikel, oder ihre Preise reichen nicht aus, um Sie zu erreichen Bei der gewünschten Summe würde die Abfrage einfach 0 Zeilen auf die gleiche Weise zurückgeben, wie ein SELECT-Ergebnis 0 Zeilen ergibt, wenn keine Zeilen zur Auswahl gefunden werden können. Wenn es im obigen Fall jedoch mehr als eine Übereinstimmung gäbe, würde dies zu mehreren Zeilen führen, wie in meinem ersten Screenshot.