Quando um algoritmo ganancioso pode resolver o problema de troca de moedas?

24

Dado um conjunto de moedas com denominações diferentes e um valor v, você deseja encontrar o menor número de moedas necessário para representar o valor v.c1,...,cn

Por exemplo, para o conjunto de moedas 1,5,10,20, isso fornece 2 moedas para a soma 6 e 6 moedas para a soma 19.

Minha principal pergunta é: quando uma estratégia gananciosa pode ser usada para resolver esse problema?


Pontos de bônus: Esta declaração está incorreta? (De: Como saber se o algoritmo ganancioso é suficiente para o problema de troca mínima de moedas? )

No entanto, este artigo tem uma prova de que, se o algoritmo ganancioso funciona para o primeiro maior denominador e o segundo maior denominador, ele funciona para todos eles, e sugere apenas o uso do algoritmo ganancioso versus o algoritmo DP ideal para verificá-lo. http://www.cs.cornell.edu/~kozen/papers/change.pdf

Ps. observe que as respostas nesse tópico são incrivelmente ruins - foi por isso que fiz a pergunta novamente.

The Unfun Cat
fonte
Para o problema da mochila binária, existe um critério facilmente formulável: o algoritmo ganancioso resolve o problema se, para todas as denominações, . Não é tão fácil para troca de moedas (mochila com variáveis ​​integrais arbitrárias). Você precisa de uma exposição de Magazine, Nemhauser e Trotter? ci>Σj=1i1cj
Dmitri Chubarov
2
A declaração no artigo de Dexter Kozen diz que se o algoritmo ganancioso concorda com o ideal para todos , ele fornecerá uma solução ótima para v arbitrário . Não vejo nada de errado com esta afirmação. v<cn1+cnv
Dmitri Chubarov
@Dmitri Chubarov Obrigado, agora eu entendo como o bônus q funciona. É semelhante a forte indução? Quanto à sua outra pergunta, gostaria de uma resposta que dê uma solução e, de preferência, uma prova.
The Unfun Cat
Voto a questão e, se ninguém entrar, resuma o MNT com alguns exemplos no fim de semana.
Dmitri Chubarov
Veja também esta questão relacionada ; em particular, o artigo vinculado por Shallit pode ser interessante.
Raphael

Respostas:

13

Um sistema de moedas é canônico se o número de moedas dado em troca pelo algoritmo ganancioso for ideal para todos os valores.

O artigo D. Pearson. Algoritmo de tempo polinomial para o problema de mudança. O Operations Reseach Letters, 33 (3): 231-234, 2005 oferece um algoritmo para decidir se um sistema de moedas é canônico, onde n é o número de diferentes tipos de moedas. Do resumo:O(n3)n

Em seguida, derivamos um conjunto de valores possíveis que devem conter o menor contra-exemplo. Cada um pode ser testado com operações aritméticas O ( n ) , fornecendo um algoritmo O ( n 3 ) .O(n2)O(n)O(n3)

O artigo é bastante curto.

cc

O(n2)n

Há também alguma discussão nesta questão .

Mark Dominus
fonte
Obrigado. Vejo que a pergunta está muito mais envolvida do que pensei - acho que é por isso que você não publicou os critérios reais? Minha idéia de que "se todas as moedas são múltiplas uma da outra, o algoritmo ganancioso fornece um resultado ideal" era obviamente muito simples.
The Unfun Cat
Não publiquei os critérios reais porque não me lembro de imediato e não tive tempo de reler o artigo. Obviamente, você deve editar minha resposta.
Mark Dominus
Li a resposta e o artigo algumas vezes, mas não consegui encontrar critérios legíveis por humanoscanonical coin system . Seria ótimo se você pudesse adicionar um exemplo, ou seja, como testar o sistema sugerido1,5,10,20
The Godfather