Programmazione dinamica - Decisione cambiamento monete

Question

Sto rivedendo alcune vecchie note del mio corso sugli algoritmi e i problemi di programmazione dinamica mi sembrano un po 'complicati. Ho un problema in cui abbiamo una scorta illimitata di monete, con alcune denominazioni x1, x2, ... xn e vogliamo cambiare per qualche valore X. Stiamo provando a progettare un programma dinamico per decidere se il cambiamento per X può essere fatto o meno (non minimizzando il numero di monete, o restituendo quali monete, solo vero o falso).

Ho fatto qualche pensiero su questo problema, e posso vedere un metodo iterativo di fare questo in cui è qualcosa di simile ...

MakeChange(X, x[1..n this is the coins]) 
    for (int i = 1; i < n; i++) 
    { 
     if ((X - x[i] ==0) || MakeChange(X - x[i])) 
      return true; 
    } 
    return false; 

Conversione di questo un programma dinamico non viene così facilmente a me . Come potrei avvicinarmi a questo?

Answer 1

Il tuo codice è un buon inizio. Il solito modo di convertire una soluzione ricorsiva in una di programmazione dinamica è farlo "dal basso verso l'alto" anziché "dall'alto verso il basso". Cioè, se la tua soluzione ricorsiva calcola qualcosa per una X particolare usando valori per x più piccoli, calcola invece la stessa cosa a partire da a x più piccola e mettila in una tabella.

Nel tuo caso, modifica la funzione ricorsiva di MakeChange in una tabella canMakeChange.

canMakeChange[0] = True 
for X = 1 to (your max value): 
    canMakeChange[X] = False 
    for i=1 to n: 
    if X>=x[i] and canMakeChange[X-x[i]]==True: 
     canMakeChange[X]=True 

Answer 2

Se si scrive in modo ricorsivo, va bene, basta usare la ricerca basata sulla memoria. è necessario memorizzare ciò che avete calcolato, che non sarà calcolato di nuovo

int memory[#(coins)]; //initialize it to be -1, which means hasn't been calculated 
MakeChange(X, x[1..n this is the coins], i){ 
    if(memory[i]!=-1) return memory[i]; 
    for (int i = 1; i < n; i++) 
    { 
     if ((X - x[i] ==0) || MakeChange(X - x[i], i)){ 
      memory[i]=true; 
      return true; 
     } 
    } 
    return false; 
} 

Answer 3

Basta aggiungere un passo Memoizzazione alla soluzione ricorsiva, e l'algoritmo dinamica cade proprio fuori di esso. L'esempio che segue è in Python:

cache = {} 
def makeChange(amount, coins): 
    if (amount,coins) in cache: 
     return cache[amount, coins] 
    if amount == 0: 
     ret = True 
    elif not coins: 
     ret = False 
    elif amount < 0: 
     ret = False 
    else: 
     ret = makeChange(amount-coins[0], coins) or makeChange(amount, coins[1:]) 
    cache[amount, coins] = ret 
    return ret 

Naturalmente, è possibile utilizzare un decoratore per l'auto-Memoize, portando a codice più naturali:

def memoize(f): 
    cache = {} 
    def ret(*args): 
     if args not in cache: 
      cache[args] = f(*args) 
     return cache[args] 
    return ret 
@memoize 
def makeChange(amount, coins): 
    if amount == 0: 
     return True 
    elif not coins: 
     return False 
    elif amount < 0: 
     return False 
    return makeChange(amount-coins[0], coins) or makeChange(amount, coins[1:]) 

Nota: anche il non-programmazione dinamica versione hai postato tutti i tipi di bug di casi limite, ecco perché makeChange è leggermente più lungo del tuo.

Answer 4

Nel caso generale, dove i valori della moneta può essere arbitraria, il problema si sta presentando è chiamato Knapsack Problem, ed è noto per appartenere a NP-completa (Pearson, D. 2004), in modo quindi non è risolvibile in tempo polinomiale come la programmazione dinamica.

Prendere l'esempio patologico di x [2] = 51, x [1] = 50, x [0] = 1, X = 100. Quindi è necessario che l'algoritmo "consideri" le possibilità di apportare modifiche con coin x [2], alternativamente facendo il cambiamento iniziando con x [1]. Il primo passaggio utilizzato con monete nazionali, altrimenti noto come Greedy Algorithm - con lo, "usa la moneta più grande in meno del totale di lavoro", non funzionerà con monete patologiche. Invece, tali algoritmi sperimentano un'esplosione combinatoria che li qualifica in NP-completo.

Per determinati accordi con valori di monete speciali, come praticamente tutti quelli in uso effettivo e incluso il sistema fittizio X [i + 1] == 2 * X [i], esistono algoritmi molto veloci, anche O (1) nel caso fittizio dato, per determinare il risultato migliore. Questi algoritmi sfruttano le proprietà dei valori delle monete.

Non sono a conoscenza di una soluzione di programmazione dinamica: quella che sfrutta soluzioni secondarie ottimali come richiesto dal motivo di programmazione. In generale, un problema può essere risolto solo con una programmazione dinamica, se può essere scomposto in sotto-problemi che, quando sono risolti in modo ottimale, possono essere ricomposti in una soluzione che è provabilmente ottimale. Cioè, se il programmatore non può dimostrare matematicamente ("dimostrare") che la ricomposizione ottimale delle sotto-soluzioni del problema si traduce in una soluzione ottimale, allora la programmazione dinamica non può essere applicata.

Un esempio comunemente dato di programmazione dinamica è un'applicazione per moltiplicare più matrici. A seconda delle dimensioni delle matrici, la scelta di valutare A · B · C sussiste una delle due forme equivalenti: ((A · B) · C) o (A · (B · C)) porta ai calcoli di diverse quantità di moltiplicazioni e aggiunte. Cioè, un metodo è più ottimale (più veloce) rispetto all'altro metodo. La programmazione dinamica è un motivo che calcola i costi computazionali di diversi metodi ed esegue i calcoli effettivi in ​​base a un programma (o programma) calcolato dinamicamente in fase di esecuzione.

Una caratteristica fondamentale è che i calcoli vengono eseguiti in base alla pianificazione calcolata e non da un'enumerazione di tutte le combinazioni possibili, indipendentemente dal fatto che l'enumerazione sia eseguita in modo ricorsivo o iterativo. Nell'esempio della moltiplicazione delle matrici, ad ogni passo, viene scelta solo la moltiplicazione meno costosa. Di conseguenza, i possibili costi delle pianificazioni sub-ottimali a costo intermedio non vengono mai calcolati. In altre parole, la pianificazione non viene calcolata cercando tutte le pianificazioni possibili per l'ottimale, ma piuttosto sviluppando in modo incrementale una pianificazione ottimale dal nulla.

La nomenclatura "programmazione dinamica" può essere confrontata con "programmazione lineare" in cui "programma" viene anche utilizzato nel senso che significa "programmare".

Per ulteriori informazioni sulla programmazione dinamica, consultare il più grande libro sugli algoritmi a me noto, "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein. "Rivest" è la "R" di "RSA" e la programmazione dinamica è solo un capitolo dei punteggi.

Cover of the recommended book. http://ecx.images-amazon.com/images/I/41hJ7gLDOmL._SL500_AA300_.jpg

Answer 5

Questa carta è molto rilevante: http://ecommons.library.cornell.edu/handle/1813/6219

Fondamentalmente, come altri hanno detto, facendo cambiare ottimale pari a una X arbitrario con denominazione arbitraria insiemi è NP-hard, cioè programmazione dinamica non cede un algoritmo tempestivo. Questo documento propone un algoritmo polinomiale (ovvero, polinomiale nella dimensione dell'input, che è un miglioramento rispetto agli algoritmi precedenti) per determinare se l'algoritmo greedy produce sempre risultati ottimali per un determinato insieme di denominazioni.

Answer 6

La mia soluzione di seguito è un approccio avido che calcola tutte le soluzioni e memorizza nella cache l'ultima ottimale. Se la soluzione di esecuzione corrente è già più grande della soluzione memorizzata nella cache, interrompere il percorso. Nota, per la migliore denominazione della performance dovrebbe essere in ordine decrescente.

import java.util.ArrayList; 
import java.util.List; 

public class CoinDenomination { 

    int denomination[] = new int[]{50,33,21,2,1}; 
    int minCoins=Integer.MAX_VALUE; 
    String path; 

    class Node{ 
     public int coinValue; 
     public int amtRemaining; 
     public int solutionLength; 
     public String path=""; 
     public List<Node> next; 

     public String toString() { return "C: "+coinValue+" A: "+amtRemaining+" S:"+solutionLength;} 
    } 

    public List<Node> build(Node node) 
    { 
     if(node.amtRemaining==0) 
     { 
      if (minCoins>node.solutionLength) { 
       minCoins=node.solutionLength; 
       path=node.path; 
      } 
      return null; 
     } 

     if (node.solutionLength==minCoins) return null; 
     List<Node> nodes = new ArrayList<Node>(); 
     for(int deno:denomination) 
     { 
      if(node.amtRemaining>=deno) 
      { 
       Node nextNode = new Node(); 
       nextNode.amtRemaining=node.amtRemaining-deno; 
       nextNode.coinValue=deno; 
       nextNode.solutionLength=node.solutionLength+1; 
       nextNode.path=node.path+"->"+deno; 
       System.out.println(node); 
       nextNode.next = build(nextNode); 
       nodes.add(node); 

      } 
     } 

     return nodes; 
    } 

    public void start(int value) 
    { 
     Node root = new Node(); 
     root.amtRemaining=value; 
     root.solutionLength=0; 
     root.path="start"; 
     root.next=build(root); 
     System.out.println("Smallest solution of coins count: "+minCoins+" \nCoins: "+path); 
    } 

    public static void main(String args[]) 
    { 
     CoinDenomination coin = new CoinDenomination(); 
     coin.start(35); 
    } 
} 

Answer 7

Ecco C# versione appena per riferimento per trovare il numero minimo di monete necessarie per la data somma:

(si può fare riferimento al mio blog @http://codingworkout.blogspot.com/2014/08/coin-change-subset-sum-problem-with.html per maggiori dettagli)

public int DP_CoinChange_GetMinimalDemoninations(int[] coins, int sum) 
     { 
      coins.ThrowIfNull("coins"); 
      coins.Throw("coins", c => c.Length == 0 || c.Any(ci => ci <= 0)); 
      sum.Throw("sum", s => s <= 0); 
      int[][] DP_Cache = new int[coins.Length + 1][]; 
      for (int i = 0; i <= coins.Length; i++) 
      { 
       DP_Cache[i] = new int[sum + 1]; 
      } 
      for(int i = 1;i<=coins.Length;i++) 
      { 
       for(int s=0;s<=sum;s++) 
       { 
        if (coins[i - 1] == s) 
        { 
         //k, we can get to sum using just the current coin 
         //so, assign to 1, no need to process further 
         DP_Cache[i][s] = 1; 
        } 
        else 
        { 
         //initialize the value withouth the current value 
         int minNoOfCounsWithoutUsingCurrentCoin_I = DP_Cache[i - 1][s]; 
         DP_Cache[i][s] = minNoOfCounsWithoutUsingCurrentCoin_I; 
         if ((s > coins[i - 1]) //current coin can particiapte 
          && (DP_Cache[i][s - coins[i - 1]] != 0)) 
         { 
          int noOfCoinsUsedIncludingCurrentCoin_I = 
           DP_Cache[i][s - coins[i - 1]] + 1; 
          if (minNoOfCounsWithoutUsingCurrentCoin_I == 0) 
          { 
           //so far we couldnt identify coins that sums to 's' 
           DP_Cache[i][s] = noOfCoinsUsedIncludingCurrentCoin_I; 
          } 
          else 
          { 
           int min = this.Min(noOfCoinsUsedIncludingCurrentCoin_I, 
            minNoOfCounsWithoutUsingCurrentCoin_I); 
           DP_Cache[i][s] = min; 
          } 
         } 
        } 
       } 
      } 
      return DP_Cache[coins.Length][sum]; 
     }