硬币更换DP解决方案，用于跟踪硬币

Question

尝试为一般硬币更换问题编程一个DP解决方案，该解决方案还可以跟踪使用的硬币。到目前为止，我一直在努力给我所需的最低硬币数量，但不知道如何获得使用了哪些硬币以及使用了多少次。我尝试设置另一个表（布尔值），如果硬币被使用，但这似乎不能正常工作。有什么想法吗？

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

以下内容在Python中似乎有效：

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

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 3

试试这个解决方案，它只使用了O（M）内存，复杂度为O（N*M）：

   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;
    }