Hi
What you are looking for is exactly the 0-1 knapsack problem. This
problem can be solved in O ( n W ) time using dynamic programming ...
where 'W' is the amount you want ... i.e. 'N' .. and 'n' is the
number of items you have.
So now the way you can do it is ... first convert the $ to cents ...
say you want 'N' cents with a tolerance of 'T' cents. The algo is as
follows:
1. Create an array of size (N+T) .. say A[1.. N+T] and set it all to zeros
2. set A[0] = 1;
3. for each item x do
for pos = N+T downto cost(x) do ...
if A[ pos - cost ( x ) ] = 1 then
A[ pos ] = 1
4. At the end ... traverse from A [ N ] to A [ N + T ] ... and see
which position is set to 1 ... that is your answer ..
If you want the matches as well ... then instead of just setting ones
and zeroes ... maitain a set of items at each position.
-Dhyanesh
On 11/22/05, Jen <[EMAIL PROTECTED]> wrote:
>
> There is a listing of $ amounts (maybe 300-400 items). The amounts in
> the list may or may not be unique. Given an arbitrary number (N), I
> want to find the item(s) in the listing that come the closest to being
> a match within a tolerance (T) without being less than N.
>
> Optimally, I would like to find one match that does not exceed T.
> However, that will not always be possible
>
> A basic example:
>
> Tolerance (T) = 1000.00
> Items A- F represent a small subset of the $ listings
>
> A - 20,295.13
> B - 35,985.55
> C - 10,195.69
> D - 28,655.78
> E - 40,144.66
> F - 32,490.50
>
>
>
> 1. Amount = 35,102.55
> Best Match = B (35,985.55) Because even though it is greater than
> 35,102.55 it does not exceed the tolerance
>
>
>
> 2. Amount = 42,674.12
> Best Match = C and F (10,195.69 + 32,490.50) The two combined are
> greater than the requested sum, but do not exceed the tolerance.
>
>
> It's easy to "eyeball" the best match within a tolerance, but I need a
> systematic way to determine "best combination". Any ideas?
>
>
