I'm looking for an algorithm that I can use for combining values in array, to get as close as possible to "another value".
For instance, the number I want to find out what combination that gives the closes result to is 2.5. And my array is [0.5, 1.0, 1.5, 2.0, 3.0]
. The combination in this case would be 2.0+0.5
.
2.7 would yield the same combo (2.5 is the closest), while 3.7 would yield 3.0+0.5
and 7.0 would be 3.0+3.0+1.0
.
I've been reading up on different algorithms to create available combinations and such – for instance this one: https://codereview.stackexchange.com/questions/7001/better-way-to-generate-all-combinations However, I'm having difficulties to write a function that allows for the same value to be used multiple times (like my example with 7.0). This makes the number of combinations quite large.
Anyone having a good example tucked away? Or have any pointers to give?
EDIT @zkar told me about the "knapsack problem". I may add that for my example, the sought after value are in a specified range (1.0 and 10.0) – which limits the the combinations somewhat.
You can try this simple algorithm (JSFiddle demo):
/**
* @param src {Array} List of available values
* @param val {Number} Target value
* @returns {Array}
*/
function get_combinations(src, val)
{
var result = [];
var source = src.slice();
source.sort();
while (val > 0)
{
for (var i = source.length - 1; i >= 0; i--)
{
if (source[i] <= val || i == 0)
{
val = val - source[i];
result.push(source[i]);
break;
}
}
}
return result;
}
Your problem is a mixture of Coin Problem and Knapsack Problem
If Coins are used only Once:
Given a set of values S, n = |S|, m: value to approximate
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
This algorithm runs in Time: O(|S|2) ~ O(n2)
The Set BEST will have n solutions, for each K: 1..n
for K: you have the optimal choice at that stage
to find the complete solution:
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
If Coins can be re-used:
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
In 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;
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With