Verpackungsproblem mit Einschränkungen auf Artikelwerte

Question

gegeben $ N $ Elemente mit Gewichten $ w_1, ..., w_n $ und Werte < Span-Klasse="Math-Container"> $ v_1, ..., v_n $ , und eine Gewichtsgrenze $ W $ , der Zweck ist immer noch maximiert der Gesamtwert der zu transportierenden Elemente (während der Gewichtsgrenze nicht überschreitet). Jetzt ist eine neue Einschränkung, sobald ein Element mit dem Wert $ v_i $ genommen wird, alle Elemente, deren Wert größer ist als $ v_i $ muss ebenfalls genommen werden. (Es ist in Ordnung, anzunehmen, dass alle $ v_i $ 's unterschiedlich sind)

Mein Zweck ist es, dies in $ O (n) $ Time zu erreichen, und hier ist mein Versuch (Angenommen, der Eingang ist ein Array $ A $ von Tupel $ (w_i, v_i) $ ):

.

1. Berechnen des Gesamtgewichts der Elemente: $ w _ {\ mathrm {total}} \ ruft \ sum_ {i= 1} ^ n w_i $ ;

2. während $ (w _ {\ mathrm {total}}> w) $ do:

   2.1 $ p \ bekommt $ Median der Werte in $ A $ ;

   2.2 $ r \ bekommt $ Elemente, deren Wert größer ist als $ P $ ; .

   2.3 $ l \ bekommt ein \ setminus r $ ; (Elemente, deren Wert kleiner ist als $ P $ )

   2.4 $ w_r \ bekommt $ $ \ sum_ {a [i] \ in r} w_i $ ;

   2.5 $ w _ {\ mathrm {total}} \ erhält w_r $ ;

   2.6 $ a \ erhält r $ ;

3. $ w \ bekommt w- w _ {\ mathrm {total}} $ ; (die verbleibende Kapazität)

4. Wiederholen Schritt 2 für das Array $ L $ , Erstellen des Arrays $ l '$ ;

5. return $ l '\ cup A $ ;

Beachten Sie, dass der Algorithmus zum Finden der Mediankosten lineare Zeit.

Ich vermute, mein Algorithmus kostet $ o (n) $ Zeit seit, für jede Iteration in jeder While-Schleife, die Eingangsgröße halbiert, aber ich bin nicht 100% zuversichtlich davon. Kostet dieser Algorithmus also wirklich lineare Zeit? Wenn nicht, welche Änderungsanträge können gemacht werden, oder gibt es eine allgemeine Idee, um einen solchen Algorithmus zu entwerfen, der lineare Zeit kostet? Jede Hilfe wird sehr geschätzt! :)

Answer 1

Ja, Ihr Algorithmus läuft in $ o (n) $ Uhrzeit, wenn Sie den Median des Median-Algorithmus verwenden. Sie können das für sich selbst beweisen, indem Sie Ihren Algorithmus betrachten und darauf hinweisen, dass in jeder Schleife die Größe des Arrays, das wir in Betracht ziehen, in Halven geschnitten wird. Und die Laufzeit des Schleifenkörpers ist $ O (n) $ (wenn wir den Median von Medianen und Array verwenden, das Kopieren / Filtern verwendet wird, ist $ O (n) $ ohnehin). Jetzt erhalten wir folgende Summe:

$$ \ SUM_ {i= 0} ^ {\ log (n)} \ frac {n} {2 ^ i} \ leq \ sum_ {i= 0 ^ ^ {\ fashy} \ frac {n} {2 ^ i}= n \ cdot \ sum_ {i= 0} ^ {\ fly} \ frac {1} {2 ^ i}= 2n \ in o (n) $$

Der $ \ log (n) $ stammt von der Tatsache, dass Sie nur die Array-Größe $ log ( n) $ Zeiten in Hälften, bis Sie mit $ 1 $ ankommen (da $ 2 ^ {\ log (n) }= n $ ). Jede Laufzeit der Summe drückt die Kosten einer Ausführung des Schleifenkörpers aus.