Wyprzedaż Boba (zmiana kolejności par z ograniczeniami w celu zminimalizowania sumy produktów)

Jakiś czas temu zadałem to pytanie na temat Przepełnienia stosu: Problem: sprzedaż Boba . Ktoś zasugerował także opublikowanie pytania tutaj.

Ktoś już zadał tutaj pytanie związane z tym problemem - minimalna waga lasów danej liczności - ale o ile rozumiem, nie pomaga mi to z moim problemem. Warto również przyjrzeć się najwyżej ocenianej odpowiedzi na StackOverflow.

Oto pełna kopia mojego pytania StackOverflow. Prawdopodobnie jest on nieodpowiednio sformułowany dla tej witryny (cholera, czuję się nieodpowiednio niewykształcony po prostu pytając go tutaj), więc możesz go edytować:

Uwaga: jest to streszczenie przeredagowania rzeczywistego problemu dotyczącego zamawiania rekordów w pliku SWF. Rozwiązanie pomoże mi ulepszyć aplikację typu open source.

Bob ma sklep i chce sprzedać. Jego sklep niesie ze sobą szereg produktów i ma na magazynie pewną liczbę całkowitą sztuk każdego produktu. Ma również wiele etykiet cenowych montowanych na półce (tyle ile produktów), z nadrukowanymi już cenami. Może umieścić dowolną etykietę cenową na dowolnym produkcie (cena jednostkowa za jeden produkt za całe zapasy tego produktu), jednak niektóre produkty podlegają dodatkowym ograniczeniom - każdy taki produkt nie może być tańszy niż określony inny produkt.

Musisz znaleźć sposób ułożenia etykiet cenowych, aby całkowity koszt wszystkich towarów Boba był jak najniższy. Całkowity koszt to suma przypisanej etykiety produktu każdemu produktowi pomnożona przez ilość tego produktu w magazynie.

Dany:

• N - liczba produktów i etykiet cenowych
• S _i , 0 ≤ i <N - ilość w magazynie produktu o indeksie i (liczba całkowita)
• P _j , 0 ≤ j <N - cena na etykiecie ceny z indeksem j (liczba całkowita)
• K - liczba dodatkowych par wiązań
• A _k , B _k , 0 ≤ k <K - wskaźniki produktu dla dodatkowego ograniczenia
  • Dowolny indeks produktu może pojawić się co najwyżej raz w B. W związku z tym wykres utworzony przez tę listę przylegania jest w rzeczywistości zbiorem ukierunkowanych drzew.

Program musi znaleźć:

• M _i , 0 ≤ i <N - odwzorowanie z indeksu produktu na indeks etykiety ceny (P _{M i} to cena produktu i )

Aby spełnić warunki:

1. P _{M A k} ≤ P _{M B k} , dla 0 ≤ k <K
2. Σ (S _i × P _{M i} ) dla 0 ≤ i <N jest minimalne

Pamiętaj, że gdyby nie pierwszy warunek, rozwiązaniem byłoby po prostu sortowanie etykiet według ceny i produktów według ilości oraz bezpośrednie dopasowanie obu.

Typowe wartości wejściowe to N, K <10000. W prawdziwym problemie istnieje tylko kilka różnych cen (1,2,3,4).

Oto przykład, dlaczego najprostsze rozwiązania (w tym sortowanie topologiczne) nie działają:

$\$$$\$$

Optymalne rozwiązanie to:

Price, $   1  2  3  4  5  6  7  8  9 10
Qty        9  8  7  6  1 10  5  4  3  2

$\$$

Wysłałem to również na twoje oryginalne pytanie dotyczące przepełnienia stosu:

Problem jest NP-zupełny w ogólnym przypadku. Można to pokazać poprzez redukcję 3-partycji (która jest wciąż silną NP-pełną wersją pakowania bin).

Niech w ₁ , ..., w _n będzie wagami obiektów instancji z 3 partycjami, niech b będzie rozmiarem bin, a k = n / 3 liczbą pojemników, które mogą zostać wypełnione. W związku z tym istnieje podział na 3 części, jeśli obiekty można podzielić na partycje, tak aby na pojemnik przypadały dokładnie 3 obiekty.

Do redukcji, ustawiamy N = kb i każdy kosz jest reprezentowany przez b etykiet cenowych w tej samej cenie (myślę P _i rośnie z każdym b th etykiecie). Niech t _i , 1 ≤ i ≤ k , będą ceną etykiet odpowiadających i -temu binowi. Dla każdego w _i mamy jeden produkt S _j ilości w _i + 1 (nazwijmy to produktem głównym w _i ) i inny w _i - 1 produkty o ilości 1, które muszą być tańsze niż S _j (nazywaj te produkty urlopu).

Do T _i = (2B + 1) ⁱ , 1≤ i ≤ k , jest 3 partycji wtedy i tylko wtedy, jeśli Bob może sprzedawać na 2b Ď _{1≤ i ≤ k} t _i :

• Jeśli nie jest to rozwiązanie na 3 strefy: wówczas wszystkie b produkty odpowiednie do obiektów w _I , w _J , W _L , które są przypisane do tego samego pojemnika może być znakowany w tym samym cenę, bez naruszania ograniczeń. Zatem rozwiązanie ma koszt 2b Ď _{1≤ i ≤ k} t _I (od całkowitej ilości produktów z ceną t _i jest 2b ).
  
• Zastanów się nad optymalnym rozwiązaniem Wyprzedaży Boba. Po pierwsze zauważ, że w każdym rozwiązaniu więcej niż 3 produkty root miały ten sam znak cenowy, dla każdego takiego produktu root, który jest „za dużo”, jest tańsza metka, która przykleja się do mniej niż 3 produktów root. Jest to gorsze niż jakiekolwiek rozwiązanie, jeśli istnieją dokładnie 3 produkty root na etykietę cenową (jeśli istnieją).
  Teraz nadal może być rozwiązanie Wyprzedaży Boba z 3 etykietami korzeniowymi na cenę, ale ich produkty wyjściowe nie noszą takich samych etykiet cenowych (pojemniki jakby się przepływały). Powiedz, że najdroższa etykieta cenowa oznacza główny produkt w _i, który ma tańszy oznaczony produkt urlopowy. Oznacza to, że 3 etykiety główne w _i , w _j , w _loznaczone najdroższą ceną nie sumują się do b . Dlatego całkowity koszt produktów oznaczonych tą ceną wynosi co najmniej 2b + 1 .
  W związku z tym, rozwiązanie takie posiada kosztów t _k (2B + 1) + kilka innych kosztów przypisania. Ponieważ koszt optymalny dla istniejącej partycji jest 3- 2b Ď _{1≤ i ≤ k} t _i musimy pokazać, że po prostu rozważyć przypadek jest gorzej. Tak jest w przypadku, gdy t _k > 2b Ď _{1≤ i ≤ k-1} t _I (zauważ, że jest to k-1 w sumie teraz). Ustawienie t _i= (2b + 1) ⁱ , 1 ≤ i ≤ k , tak jest w tym przypadku. Dotyczy to również, jeśli nie najdroższa cena to „zła”, ale jakakolwiek inna.

Jest to więc część destrukcyjna ;-) Jednak jeśli liczba różnych metek ceny jest stała, można użyć programowania dynamicznego, aby rozwiązać ją w czasie wielomianowym.

To kontynuacja odpowiedzi Gero . Chodzi o to, aby zmodyfikować jego konstrukcję, aby wykazywała dużą twardość NP.

$t_i=(2b+1)^i$$t_i=i$$P=2b\sum_{1\leq i \leq k} t_i$

$w_i-1$$P$$P$

Dlatego możliwe jest osiągnięcie żądanej nagrody tylko wtedy, gdy wszystkie produkty z liści mają tę samą nagrodę co produkt główny, co oznacza, że ​​istnieje 3-partycja.

$k$$f(k)\cdot n^{O(1)}$$n^{O(k)}$

Przesłano również do pierwotnego pytania dotyczącego przepełnienia stosu.

To brzmi jak pytanie teorii gier. W takim przypadku bardzo prostym rozwiązaniem z użyciem siły brutalnej jest:

Załóżmy, że ograniczenia reprezentują niektóre niezmienniki formy

S-> AkSBk | AkBkS | SAkBk

Rozwiązaniem jest dodawanie najpierw ograniczeń, a następnie elementów. Np .: Powiedzmy, że n = 10 i istnieją 2 ograniczenia, A1B1 i A2B2. Następnie do węzła głównego jest troje dzieci (poziom 2). Każdy z tych 3 węzłów będzie miał 7 dzieci na poziomie 3, każdy z 21 ma 6 na poziomie 4 itd. Zasadniczo przeglądasz wszystkie możliwe kombinacje.

                A1B1 --- Poziom 1 
               / | \
              / | \
             / | \
            / | \
    A1A2B2A1 A1B1A2B2 A2B2A1B1 --- Poziom 2

i wyhoduj drzewo. Chociaż na początku wygląda to na okropne rozwiązanie, czuję, że można zrezygnować z gonienia za bardzo drogimi liśćmi, używając heurystyki i przycinania ...