For reference sake, your problem put mathematically:
Given an integer T and a vector c (|c| <= 500), solve for vector a and integer b:
(all numbers are non-negative integers)
a0.c0 + a1.c1 + a2.c2 + ... = T.b
a0 + a1 + a2 + ... = b
each ai <= 10000
b > 0
Additional constraint: minimize b
For your example:
c
is {6,2}, T
is 3, a
comes to {1, 3} and b
comes to 4.
It feels like there should be a mathematical way to solve it (though I doubt there is).
Brute force will be way too slow. For 500 types up to 10000 occurrences each, we're talking about 500^10000, which is ... a lot.
I'm thinking CSP or hill climbing.
Hill climbing is easy enough to implement - you will basically just start with some random selection of elements, then add and remove elements to get closer to the target.
The wiki page on integer programming has a bit of useful information.