最小硬币找零(无限,未绑定)打印值

问题描述 投票:0回答:1

下面的函数获得应该总结或覆盖量的硬币的最小数目。例如:如果我有硬币:[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 - >容量:6总数:18 - >容量:11总:2 - >容量:6总:6 - >容量:6总:7 - >容量:11总计:24 - >容量:6总: 12 - >容量:6总计:13 - >容量:6

现在的公式应该是拿到面额是:循环到:最大(总) - 容量(总),直到结果小于或等于零。

面额是:用于每个能力(总)

algorithm dynamic-programming minimum knapsack-problem coin-change
1个回答
1
投票

记住项capacity[i]或索引i提供了最好的subres

在地图的附加字段存储。

在结束放松从地图最好的序列。

© www.soinside.com 2019 - 2024. All rights reserved.