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

Odpowiedzi:

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