Steven Bethard wrote:
I have a list of dictionaries. Each dictionary holds counts of various 'words', e.g.:
py> countdicts = [ ... dict(a=9, b=9, c=9), ... dict(a=8, b=7), ... dict(a=4, b=5, c=12)]
I need to select dicts with the constraint that the number of each 'word' totalled over all selected dicts doesn't exceed a given MAX_VALUE. Right now, I do this by:
Not that you can't still improve performance of course, but this is an NP-complete problem if you didn't know, so don't bang your head too hard...
Yeah, it seemed a lot like one of those box-packing type problems, so if it's NP-complete, it wouldn't surprise me. That's one of the reasons I mentioned trying A* in one of my other responses. However, in retrospect, I don't think I can apply A* because I don't really have a "goal state". I could call a selection where all "words" had MAX_VALUE counts a "goal state", but I'm not guaranteed that such a state always exists (and if it doesn't A* just degenerates into an exhaustive search).
Anyway, do you know what name this problem is usually discussed under? If I knew what to google for, I could probably find at least a few simple heuristics to try...
Thanks again,
STeVe -- http://mail.python.org/mailman/listinfo/python-list
