Следующая функция получает минимальное количество монет, которое должно суммироваться или покрывать сумму.Например: если у меня есть монеты: [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
Теперь формула для получения номиналов должна быть следующей: Loop to: Max (total) - Capacity (total), пока результат не станет меньше или равен нулю.
Номиналы:емкость (общая) для каждого