Czy ten problem jest NP-trudny?

Question

Próbuję wymyślić rozsądny algorytm dla tego problemu:

Załóżmy, że masz kilka piłek. Każda piłka ma co najmniej jeden kolor, ale może również być wielokolorowa. Każda piłka ma również numer na niej. Istnieje również garść pudełek, z których każdy ma tylko jeden kolor. Celem jest maksymalizacja sumę liczb od kul w pudełkach, a jedyne zasady to:

• , aby umieścić piłkę w polu, to musi przynajmniej mieć kolor pudełka za na nim
• możesz umieścić tylko jedną piłkę w każdym polu .

Na przykład niebieską i zieloną piłkę można umieścić w niebieskim polu lub zielonym pudełku, ale nie w czerwonym polu.

Wymyśliłem kilka optymalizacji, które pomagają bardzo pod względem czasu działania. Na przykład możesz sortować kulki w malejącej kolejności według wartości punktowej. Następnie, gdy przechodzisz od najwyższej liczby do najniższej, jeśli kula ma tylko jeden kolor i nie ma innych wyższych kul, które zawierają ten kolor, możesz umieścić go w tym pudełku (a tym samym usunąć to pudełko i tę piłkę z pozostałe kombinacje).

Jestem po prostu ciekawy, czy istnieje jakiś rodzaj dynamicznego algorytmu dla tego rodzaju problemu, czy też jest to tylko kłopotliwy sprzedawca w przebraniu. Czy pomogłoby mi, gdybym wiedział, że jest co najwyżej X kolorów? Każda pomoc jest bardzo doceniana. Dzięki!

---

Edit - oto prosty przykład:

Balls:

• 1 czerwona kula - 5 punktów
• 1 blue ball - 3 punkty
• 1 zielony/czerwony kulkowe - 2 punkty
• 1 zielona/niebieska kula - 4 punkty
• 1 czerwony/niebieski ball - 1 punkt

Boxes:

• 1 czerwona
• 1 niebieski
• 1 zielony

Optymalne rozwiązanie:

• czerwony piłka w czerwonym polu
• niebieską piłkę w niebieskim polu

• zielono/niebieskie kulki w zielonym polu

  wartość całkowita: 12 punktów (5 + 3 + 4)

Answer 1

Jest to szczególny przypadek maximum weight matching problem on a weighted bipartite graph.Zbuduj wykres, którego lewe wierzchołki odpowiadają kulom, których prawe wierzchołki odpowiadają polom i krawędziom łączącym kulę oraz polu o wadze V, gdzie V jest liczbą na kuli, jeśli kulkę można umieścić w pudełku, i 0 w przeciwnym razie . Dodaj dodatkowe pudełka lub kulki połączone na drugą stronę z krawędziami o wadze zerowej, dopóki nie uzyskasz tej samej liczby wierzchołków z każdej strony. Przypisanie, którego szukasz, jest określane przez zbiór krawędzi o niezerowej wadze w maksymalnym (całkowitym) ciężarze pasującym do wynikowego wykresu.

Algorytm przydziału może zostać rozwiązany w czasie O (n^3), gdzie n oznacza maksymalną liczbę kulek lub skrzynek, używając Hungarian algorithm. (BTW, powinienem złożyć oświadczenie, że wspominam tylko o węgierskim algorytmie, ponieważ jest to teoretyczny rezultat, który znam i prawdopodobnie odpowiada na pytanie w tytule, czy pierwotny problem jest NP-trudny. czy jest to najlepszy algorytm do zastosowania w praktyce.)

Answer 2

Czy próbowałeś chciwego alg? Sortuj według punktów/wartości i umieść w polu, jeśli to możliwe. Jeśli są jakieś wyjątki, im brakuje identyfikatora, tak jak je widzę.