动态规划的硬币更换问题

Question

这是我关于硬币更换问题的代码，用于打印一组硬币的总方式数和目标金额

def coin_change(coins,amount):
    table=[0 for k in range(amount+1)]
    table[0]=1
    for coin in coins:
        for x in range(coin,amount+1):
            table[x] = table[x]+ table[x-coin]
        print(table)  

    return table[amount]

我想知道是否有任何方法可以用相同的动态规划解决方案打印这些方法（借助内部构造的表或任何其他方法）

例如，如果一组硬币是[1,3,5]，目标金额是6，那么总共有4种可能的方式。[1,1,1,1,1,1,1，]，[1,1,1,3]，[3,3]，[1,5]]我希望这种方式的列表作为输出。

Answer 1

    Arrays.sort(coins);
    int dp[]=new int [amount+1];
    Arrays.fill(dp,amount+1);
    dp[0]=0;
    for(int i=0;i<=amount;i++){
        for(int j=0;j<coins.length;j++){
            
            if(coins[j]<=i){
                
                dp[i]=Math.min(dp[i], 1+dp[i-coins[j]]);
                
            }
            else
                break;
            
        }
        
        
    }
   
    return dp[amount]>amount ? -1: dp[amount];

Answer 2

您可以随时调整当前代码以生成解决方案列表。

def coin_change(coins,amount):
    table=[[] for k in range(amount+1)]
    table[0].append([]) # or table[0] = [[]], if you prefer
    for coin in coins:
        for x in range(coin,amount+1):
            table[x].extend(solution + [coin] for solution in table[x-coin])
        print(table)  

    return table[amount]

表变量现在是列表列表列表，内部列表是加起来等于给定值的硬币组合，而不仅仅是这些组合中有多少的计数。我使用传递给extend的生成器表达式，而不是添加新的组合。

Answer 3

根据您的要求编辑答案：

def combine(parent, me):
    if len(parent) == 0:
        return [[me]]
    new_list = []
    for entry in parent:
        new_list.append(entry + [me])
    return new_list


def get_ways(amount, coins):
    table = [0 for k in range(amount + 1)]
    table[0] = 1
    ways = [[] for _ in range(amount + 1)]
    for coin in coins:
        for x in range(coin, amount + 1):
            table[x] = table[x] + table[x - coin]
            ways[x].extend(combine(ways[x - coin], coin))
    print(ways[amount])
    return table[amount]


print(get_ways(6, [1, 3, 5]))

输出：

[[1, 1, 1, 1, 1, 1], [1, 1, 1, 3], [3, 3], [1, 5]]
4