最小硬币兑换（无限，未绑定）打印值

Question

例如：如果我有硬币：[6,11]，我需要最小的硬币来获得13，那么答案应该是2（11,6），这些是最小的硬币数量。

现在我需要打印组成这个答案的实际硬币。

    private int minCapacity(int capacity[], int total, Map<Integer, Integer> map)
{
    // base case 
    if (total<= 0)
    {
        return 0;
    }

    //if map contains the result means we calculated it before. Lets return that value.
    if (map.containsKey(total))
    {
        return map.get(total);
    }

    // Initialize result 
    int res = Integer.MAX_VALUE;

    for (int i = 0; i < capacity.length; i++)
    {
        //allResults.add(capacity[i]);
        int subRes = minCapacity(capacity, total- capacity[i], map);
        System.out.println("total : " + subRes + ", staff: " + capacity[i]);
        //if val we get from picking coins[i] as first coin for current total is less
        // than value found so far make it minimum.

        if (subRes < res)
        {
            res = subRes;
            coinsRes.put(total, capacity[i]);
        }

    }
    res = (res == Integer.MAX_VALUE) ? res : res + 1;

    //memoize the minimum for current total.
    map.put(total, res);
    return res;
}

这是输出：

总计： 1-

现在，公式应该是：循环到：Max（total）-容量（total），直到结果小于或等于零。

面额为：每个单位的容量（总数）

Answer 1

记住什么项目capacity[i]或indexi给出了最好的subres

将其存储在地图的其他字段中。

最后，从贴图中展开最佳序列。