下面的函数获得应该总结或覆盖量的硬币的最小数目。例如:如果我有硬币:[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
现在的公式应该是拿到面额是:循环到:最大(总) - 容量(总),直到结果小于或等于零。
面额是:用于每个能力(总)
记住项capacity[i]
或索引i
提供了最好的subres
在地图的附加字段存储。
在结束放松从地图最好的序列。