The papers I've found about the Frobenius instance problem (given a set of distinct positive integers, find the positive integer coefficients that make a linear combination of some of them add up to a given integer) seem interested in computational efficiency with very large numbers or just finding the Frobenius number.
Instead, I have an application with relatively small problems (less than a hundred numbers to obtain a sum up to a few thousands) that are likely to have many solutions, and I want to choose the best solution with various criteria such as using as many different numbers as possible, preferring to use larger numbers, minimizing the variation between coefficients, etc.
I can compromise on not finding the best solution, but not on missing a solution if one exists; my best plan so far is growing solutions by dynamic programming or with an A* search (choosing pieces that seem good), at the cost of not using the most appropriate cost functions.
I'd like to hear about previous work about
- this kind of optimization over all solutions;
- algorithms to enumerate all solutions rather than finding an arbitrary one;
- algorithms to find the number of solutions (nice to know before evaluating them brute-force);
- sensible ways to split a problem into smaller ones.
Thank you in advance.