selecting dictionaries to maximize counts

[Steven Bethard]

Brian Beck wrote:
> 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