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

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.

algorithms combinatorics greedy-algorithms 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?

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

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

Dmitri Chubarov

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

arbitrário . Não vejo nada de errado com esta afirmação.

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

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

v

$v$

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:

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 é o número de diferentes tipos de moedas. Do resumo: $O(n^3)$ $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 , fornecendo um algoritmo . $O(n^2)$ $O(n)$ $O(n^3)$

O artigo é bastante curto.

$c$ $c$

$O(n^2)$ $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