selecting dictionaries to maximize counts

[John Machin]

Steven Bethard wrote:
> I have a list of dictionaries.  Each dictionary holds counts of
various
> 'words', e.g.:

> Basically, I use a greedy approach -- adding a dict each time if I
can.
>   This leads to some suboptimal solutions given that, while the total

> counts must not exceed MAX_VALUE, I'd like them to be as close to
> MAX_VALUE as possible.  An example of data on which my select
function
> produces such a suboptimal solution:
>
> py> countdicts = [
> ...     dict(a=9, b=9, c=9),
> ...     dict(a=8, b=7),
> ...     dict(a=4, b=5, c=12)]
> py> select(countdicts, 12)
> [{'a': 9, 'c': 9, 'b': 9}]
>
> The better solution would have been to select the second two dicts --

> then all 'words' would have count 12.
>
> I don't need an optimal solution; in fact, the solution I have right
now
> is tolerable.  But if anyone knows a simple way to improve my
> performance, I'd appreciate it.  Thanks!

This is more than a bit OT but you've sucked me in :-)

You should specify a function that assigns a score to valid solutions;
it's not apparent from the wording above and the example exactly what
that function might be. Thinking through the alternatives might help
you solve the problem yourself :-)