title: Need an algorithm approach to calculate meal plan
body: <p>I’m having trouble solving a deceptively simple problem.  My girlfriend and I are trying to formulate weekly meal plans and I had this brilliant idea that I could optimize what we buy in order to maximize the things that we could make from it.  The trouble is, the problem is not as easy as it appears.  Here’s the problem statement in a nutshell:</p>
  
  <p>The problem:
  Given a list of 100 ingredients and a list of 50 dishes that are composed of one or more of the 100 ingredients, find a list of 32 ingredients that can produce the maximum number of dishes.</p>
  
  <p>This problem seems simple, but I’m finding that computing the answer is not trivial.  The approach that I’ve taken is that I’ve computed a combination of the 32 ingredients as a 100 bit string with 32 of the bits set.  Then I do a check of what dishes can be made with that ingredient number.  If the number of dishes is greater than the current maximum, I save off the list.  Then I compute the next valid ingredient combination and repeat, repeat, and repeat.</p>
  
  <p>The number of combinations of the 32 ingredients is staggering!  The way that I see it, it would take about 300 trillion years to calculate using my method.  I’ve optimized the code so that each combination takes a mere 75 microseconds to figure out.  Assuming that I can optimize the code, I might be able to reduce the run time to a mere trillion years.</p>
  
  <p>I’m thinking that a completely new approach is in order.  I'm currently coding this in XOJO (REALbasic), but I think the real problem is with approach rather than specific implementation.  Anybody have an idea for an approach that has a chance of completion during this century?</p>
  
  <p>Thanks,</p>
  
  <p>Ron</p>