Münzwechsel-DP-Lösung zum Nachverfolgen von Münzen

Question

Der Versuch, eine DP-Lösung für das allgemeine Münzwechsel-Problem zu programmieren, die auch verfolgt, welche Münzen verwendet werden. Bis jetzt habe ich es geschafft, um mir die minimale Menge an Münzen zu geben, aber ich kann nicht herausfinden, wie man welche Münzen benutzt und wie oft. Ich habe versucht, eine andere Tabelle (boolean) mit Werten einzurichten, wenn die Münze verwendet wird, aber das scheint nicht richtig zu funktionieren. Irgendwelche Ideen?

public static int minChange(int[] denom, int changeAmount) 
{ 
    int m = denom.length; 
    int n = changeAmount + 1; 

    int[][] table = new int[m][n]; 
    boolean[][] used = new boolean[m][n]; 
    for (int j = 0; j < n; j++) 
     table[m - 1][j] = j; 
    for (int i = 0; i < m; i++) 
     table[i][0] = 0; 

    for (int i = m-2; i >= 0; i--) //i denotes denominationIndex 
    { 
     for (int j = 1; j < n; j++) //j denotes current Amount 
     { 
      if (denom[i] > j) 
      { 
       table[i][j] = table[i+1][j]; 
       //used[i][j] = false; 
      } 
      else 
      { 
       table[i][j] = Math.min(1 + table[i][j-denom[i]], table[i+1][j]); 
       /*Trying table for used coins 
       if (1 + table[i][j-denom[i]] < table[i+1][j]) 
        used[i][j] = true; 
       else 
        used[i][j] = false; 
       */ 
      } 
     } 
    } 
} 

Answer 1

Die folgende scheint in Python zu arbeiten:

def g(A, n) : 
    # 
    if A == [] or n == 0 or min(A) > n : 
     return [] 

    # 
    else : 

     # 
     min_len = float("inf") 
     min_seq = None 

     # 
     for i, a in enumerate(A) : 
      if a <= n : 
       # 
       tmp = [ a ] + g(A[:i] + A[i+1:], n-a) 

       # 
       if len(tmp) < min_len : 
        min_seq = tmp 
        min_len = len(min_seq) 
     # 
     return min_seq 


# 
for i in xrange(20) : 
    # 
    A = list(nr.randint(1, 10, 5)) 
    print A, g(A[:-1], A[-1]) 

Answer 2

Sie nicht die erste Dimension Ihres dp benötigen. Sie können ein Array mit nur einer Dimension verwenden - die Summe aller verwendeten Münzen. Dann können Sie einfach den Index Ihrer zuletzt verwendeten Münze für jeden Zustand Ihres DP speichern. Was ich meine, ist so etwas wie:

int[] dp = new int[n]; 
int[] usedCoin = new int[n]; 

for (int i=0; i < n; ++i) { 
    dp[i] = -1; // state not reached 
    usedCoin[i] = -1; 
} 

dp[0] = 0; // initial state -- we can have sum 0 without any coins 
for (int coinId = 0; coinId < m; coinId++) 
    for (int sum = 0; sum + denom[coinId] < n; sum++) { 
     int newSum = sum + denom[coinId]; 
     if (dp[newSum] == -1 || dp[newSum] > 1 + dp[sum]) { 
      dp[newSum] = 1 + dp[sum]; 
      usedCoin[newSum] = coinId; 
     } 
    } 

Wenn Sie eine konkrete Zersetzung mit minimalen Menge an Münzen finden möchten, können Sie so etwas wie zu tun:

int sum = changeAmount; 
System.out.println("The used coins are:"); 
while (usedCoin[sum] != -1) { 
    System.out.print(denom[ usedCoin[sum] ].toString() + " "); 
    sum -= denom[ usedCoin[sum] ]; 
} 

Answer 3

diese Lösung Versuchen Sie, es verwendet nur O (M) Speicher und hat O (N * M) Komplexität:

public static int[] minChange(int[] denom, int changeAmount) 
    { 
     int n = denom.length; 
     int[] count = new int[changeAmount + 1]; 
     int[] from = new int[changeAmount + 1]; 

     count[0] = 1; 
     for (int i = 0 ; i < changeAmount; i++) 
      if (count[i] > 0) 
       for (int j = 0; j < n; j++) 
       { 
        int p = i + denom[j]; 
        if (p <= changeAmount) 
        { 
         if (count[p] == 0 || count[p] > count[i] + 1) 
         { 
          count[p] = count[i] + 1; 
          from[p] = j; 
         } 
        } 
       } 

     // No solutions: 
     if (count[changeAmount] == 0) 
      return null; 

     // Build answer. 
     int[] result = new int[count[changeAmount] - 1]; 
     int k = changeAmount; 
     while (k > 0) 
     { 
      result[count[k] - 2] = denom[from[k]]; 
      k = k - denom[from[k]]; 
     } 

     return result; 
    } 

Answer 4

Verwenden folgende Pseudo-Code für reco nstructing Lösung: -

solutionSet = [] 

i = denom.length-1 

j = changeAmount 

While(i>=0) { 

    if(1+table[i][j-denom[i]]<table[i+1][j]) { 
     solutionSet.add(denom[i]) 
     j = j - denom[i] 
    } 
    i-- 
} 

Hinweis: Es gibt keine Notwendigkeit, zusätzliche Speicher zu verwenden, hier andere als die Lösung

Answer 5

public static int minimumNumberOfWays(int []deno, int amount){ 
    int dp[] = new int[amount+1]; 
    dp[0]=0; 
    int []prevCoin = new int[amount+1]; 
    for(int j=1;j<=amount;j++){ 
     dp[j]=Integer.MAX_VALUE; 
     for(int i=0;i<deno.length;i++){ 
      if(deno[i]<=j && (1+dp[j-deno[i]] < dp[j])){    
       dp[j]=1+dp[j-deno[i]]; 
       prevCoin[j]=deno[i]; 
      }     
     } 
    } 

    int result = dp[amount]; 
    List<Integer> coinsAdded = new ArrayList<Integer>(); 
    for(int i=amount;i>=1;){ 
     coinsAdded.add(prevCoin[i]); 
     int j=i; 
     i=amount-prevCoin[i]; 
     amount = amount - prevCoin[j]; 
    } 
    Integer [] coins = coinsAdded.toArray(new Integer[coinsAdded.size()]); 
    System.out.println(Arrays.toString(coins)); 

Answer 6

public class CoinChange { 

    public static void main(String[] args) { 
     int[] coins = {1,2,10,5};  
     int amt = 37;  
     makeChange(coins, amt); 
    } 

    public static void makeChange(int[] coins, int amount){ 
     //Sorting the coins 
     Arrays.sort(coins); 

     int n = coins.length - 1; 


     HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); 

     while(amount > 0) 
     { 
      if(coins[n] <= amount) 
      { 
       int val = 1; 
       if(map.containsKey(coins[n])) 
       { 
        val = map.get(coins[n]); 
        val = val+1; 
       } 

       map.put(coins[n], val); 

       amount = amount - coins[n]; 

      } 
      else 
      { 
       n--; 
      } 

     } 

     for(Map.Entry<Integer, Integer> entry: map.entrySet()){ 

      System.out.println(entry.getKey() +":" + entry.getValue()); 
     } 
    } 
} 

Answer 7

public class CoinChange { 
/** 
* Get mini num of coins 
* 
* @param coinValues 
*   coins 
* @param totalMoney 
*   total money 
* @return 
*/ 
public int coinNum(int[] coinValues, int totalMoney) { 
    List<Integer> coins = new ArrayList<Integer>(); 
    coins.add(0); 
    for (int i = 1; i <= totalMoney; i++) { 
     int coin = nearestCoin(i, coinValues); 
     int coinNum = coins.get(i - coin) + 1; 
     coins.add(coinNum); 
    } 
    return coins.get(totalMoney); 
} 

/** 
* Get the coin nearest to specified value. 
*/ 
private int nearestCoin(int value, int[] coinValues) { 
    int res = 0; 
    int nearest = Integer.MAX_VALUE; 
    for (int coinValue : coinValues) { 
     if (coinValue <= value) { 
      int distance = value - coinValue; 
      if (distance < nearest) { 
       nearest = distance; 
       res = coinValue; 
      } 
     } 
    } 
    return res; 
} 

@Test 
public void test() throws Exception { 
    int res = coinNum(new int[] { 1, 2, 3, 5, 11 }, 81); 
    System.out.println(res); 
} 

}

Answer 8

/speichern benötigt * Münzenwechsel Problem

Eingang Spezifikation: First Line erwartet, dass die Menge Zweite Zeile die Anzahl der Münzen

Ouput Spezifikation angenommen wird Third Line enthält Münzen in aufsteigender Reihenfolge der Nennwerte unbegrenzt verfügbar Münzen erwartet: Jeder Fall angezeigt wird, mit die Münze mit dem niedrigsten Nennwert zuerst, dann die nächst höhere Nennwert. Fälle werden durch Linien getrennt Wenn die Menge nicht gebildet werden kann -1 gedruckt werden Hinweis: Dies ist keine DP Lösung */

#include<iostream> 
using namespace std; 
int *num,*coins,*maxC,n,amount,flag=0,stop=0; 
int sum() 
{ 
    int i=0,j; 
    int sum=0; 
    for(i=0;i<n;++i) 
     for(j=0;j<num[i];++j) 
      sum+=coins[i]; 
    return sum; 
} 
void print() 
{ 
    int i,j; 
    for(i=0;i<n;++i) 
    { 
     for(j=0;j<num[i];++j) 
      cout<<coins[i]<<" "; 
    } 
    cout<<endl; 
} 
void printNum() 
{ 
    int i; 
    for(i=0;i<n;++i) 
     cout<<num[i]<<" "; 
    cout<<endl; 
} 
void nextIter() 
{ 
    int i,j; 
    int stat=0; 
    //printNum(); //Remove the comment if you want to see the values of num array in every iteration 
    for(i=0;i<n;++i) 
    { 
     if(num[i]==0) 
      stat=1; 
     else 
     { 
      stat=0; 
      break; 
     } 
    } 
    if(stat) 
    { 
     stop=1; 
     return ; 
    } 
    for(i=n-1;i>=0;--i) 
    { 
     int dec=0; 
     if(num[i]==0) 
     { 
      dec=1; 
      num[i]=maxC[i]; 
     } 
     else 
     { 
      --num[i]; 
      return ; 
     } 
    } 
} 
int find() 
{ 
    while(!stop) 
    { 
     if(amount==sum()) 
     { 
      flag=1; 
      print(); 
     } 
     nextIter(); 
    } 
} 
int main() 
{ 
    int i; 
    cout<<"\nEnter amount:"; 
    cin>>amount; 
    cout<<"\nEnter number of coins:"; 
    cin>>n; 
    coins=new int[n]; 
    maxC=new int[n];//contains maximum number of each denomination required 
    num=new int[n];//contains current number of each denomination required 
    for(i=0;i<n;++i) 
    { 
     cin>>coins[i]; 
     num[i]=maxC[i]=amount/coins[i]; 
    } 
    find(); 
    if(!flag) 
     cout<<"-1"; 
    cout<<endl; 
    system("pause"); 
    return 0; 
}