I've been trying to construct an algorithm in PHP that in some ways resembles a subset-sum problem, but in this case, i'm not looking for an exact match, only the closest matches, as in most cases there is unlikely to be an exact match.
Let me elaborate in a little more detail. Say I own various hypothetical investments, and need to raise the sum X from existing investments. Say X = 40000.
The array of inputs are (4500, 8750, 12900) and the number of each held are (8, 10, 10).
Now, I can intuitively work out that 4500 * 8 = 36000, 12900 * 3 = 38700, but a closer match would be (4500 * 6) + 12900 = 39900.
I soon found that try to loop through each possible combination rapidly creates 10's of million of possible arrays, even more if additional inputs are added. That would not be a problem if it was just for my own purposes, but not viable for a web-application.
I'm not asking for anybody to write code for me. I'm not a mathematician, so I'm just wondering if there is a different way I could tackle this problem, or are least short-cut parts of it ?
Thanks.
