Ответ 1
Ваша проблема представляет собой смесь Проблема с монетами и Проблема с рюкзаком
Если монеты используются только один раз:
Учитывая набор значений S, n = | S |, m: значение для приближения
DEFINE BEST = { }
DEFINE SUM = 0
DEFINE K = 0
WHILE S IS NOT EMPTY DO
K = K + 1
FIND MIN { Si : |(SUM+Si) - m| is minimal }
ADD TUPLE < Si, |(SUM+Si) - m|, K > to BEST
SUM = SUM + Si
REMOVE Si from S
END-FOR
RETURN BEST
Этот алгоритм работает во времени: O (| S | 2) ~ O (n 2)
У набора BEST будет n решений, для каждого K: 1..n
для K: у вас есть оптимальный выбор на этом этапе
чтобы найти полное решение:
GIVEN BEST = { < COIN:X, DISTANCE:Y, DEGREE:K > }
DEFINE SOLUTION = { }
Y" = MINIMUM Y IN BESTi.Y for i: 1..n
KEEP ADDING BESTj.X to SOLUTION UNTILL BESTj.Y = Y" FOR j: 1..n
Если монеты можно повторно использовать:
DEFINE SOLUTION = { }
DEFINE SUM = 0
LESS = { Si : Si < m }
SORT LESS IN DESCENDING ORDER
FOR Li in LESS DO
WHILE (SUM+Li) <= m DO
SUM = SUM + Li
ADD Li TO SOLUTION
END-WHILE
IF SUM = m THEN BREAK-FOR
END-FOR
RETURN SOLUTION
В JavaScript:
function coinProblem (var coins, var value)
{
var solution = new Array();
var sum = 0;
var less = new Array();
for (var i in coins)
if (i <= value)
less.push(i);
// sort in descending order
less.sort();
less.reverse();
for (var i in less)
{
while ((sum+i) <= value)
{
solution.push(i);
sum = sum + i;
}
if (sum == value) break;
}
return solution;
}