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 :-)
--
http://mail.python.org/mailman/listinfo/python-list
