Kiedy zachłanny algorytm może rozwiązać problem zmiany monety?

Biorąc pod uwagę zestaw monet o różnych nominałach i wartości v, chcesz znaleźć najmniejszą liczbę monet potrzebną do przedstawienia wartości v. $c1, ... , cn$

Np. Dla zestawu monet 1,5,10,20 daje to 2 monety dla sumy 6 i 6 monet dla sumy 19.

Moje główne pytanie brzmi: kiedy można zastosować chciwą strategię, aby rozwiązać ten problem?

Punkty bonusowe: Czy to stwierdzenie jest po prostu nieprawidłowe? (Od: Jak stwierdzić, czy chciwy algorytm wystarcza do rozwiązania problemu minimalnej wymiany monet? )

Jednak ten dokument ma dowód, że jeśli chciwy algorytm działa dla pierwszej największej denomu + drugiej największej wartości denomu, to działa dla nich wszystkich i sugeruje użycie algorytmu chciwego w porównaniu z optymalnym algorytmem DP, aby to sprawdzić. http://www.cs.cornell.edu/~kozen/papers/change.pdf

Ps. zwróć uwagę, że odpowiedzi w tym wątku są niesamowicie nieprzyzwoite - dlatego zadałem to pytanie od nowa.

algorithms combinatorics greedy-algorithms

— The Unfun Cat
źródło

W przypadku binarnego problemu plecakowego istnieje łatwe do sformułowania kryterium: zachłanny algorytm rozwiązuje problem, jeśli dla wszystkich nominałów . Nie tak łatwo wymienić monety (plecak z dowolnymi zmiennymi całkowymi). Potrzebujesz wystawy Magazine, Nemhauser i Trotter?

c_{i} > Σ_{j = 1}^{i - 1} c_{j}

$c_i > \Sigma_{j=1}^{i-1} c_j$

— Dmitrij Chubarow

Oświadczenie w pracy Dextera Kozen'a mówi, że jeśli chciwy algorytm zgadza się z optymalnym dla wszystkich , to da optymalne rozwiązanie dla dowolnego . Nie widzę nic złego w tym stwierdzeniu.

v < c_{n - 1} + c_{n}

$v < c_{n-1} + c_n$

v

$v$

— Dmitrij Chubarow

@Dmitri Chubarov Dzięki, teraz rozumiem, jak działa bonus q. Czy to przypomina silną indukcję? Jeśli chodzi o inne pytanie, chciałbym uzyskać odpowiedź, która da rozwiązanie, a najlepiej dowód.

— The Unfun Cat

Głosuję za pytaniem i jeśli nikt nie wskoczy, podsumuję MNT kilkoma przykładami w weekend.

— Dmitrij Chubarow

Zobacz także to powiązane pytanie ; w szczególności dokument powiązany Shallit może być interesujący.

— Raphael

System monet jest kanoniczny, jeśli liczba monet podana w zamian przez chciwy algorytm jest optymalna dla wszystkich kwot.

Artykuł D. Pearson. Algorytm czasu wielomianowego dla problemu wprowadzania zmian. Operations Reseach Letters, 33 (3): 231–234, 2005 oferuje algorytm do decydowania, czy system monet jest kanoniczny, gdzie jest liczbą różnych rodzajów monet. Z streszczenia: $O(n^3)$ $n$

Następnie uzyskujemy zbiór możliwych wartości, które muszą zawierać najmniejszy kontrprzykład. Każdą z nich można przetestować za pomocą operacji arytmetycznych , co daje nam algorytm . $O(n^2)$ $O(n)$ $O(n^3)$

Papier jest dość krótki.

$c$ $c$

$O(n^2)$ $n$

W tym pytaniu matematycznym jest także trochę dyskusji .

— Mark Dominus
źródło

Dzięki. Widzę, że pytanie jest o wiele bardziej zaangażowane niż myślałem - chyba dlatego nie opublikowałeś rzeczywistych kryteriów? Mój pomysł, że „jeśli wszystkie monety są wielokrotnościami siebie, chciwy algorytm daje optymalny wynik” był oczywiście zbyt prosty.

— The Unfun Cat

Nie opublikowałem rzeczywistych kryteriów, ponieważ nie pamiętałem od razu i nie miałem czasu na ponowne przeczytanie artykułu. Oczywiście powinieneś edytować moją odpowiedź.

— Mark Dominus,

Przeczytałem odpowiedź i artykuł kilka razy, ale nie byłem w stanie znaleźć kryteriów czytelnych dla człowiekacanonical coin system . Byłoby wspaniale, gdybyś mógł dodać przykład, tj. Jak przetestować sugerowany system1,5,10,20

— Ojciec Chrzestny