title: Is there a better way to guess possible unknown variables without brute force than I am doing? Machine learning?
body: <p>I have a game with the following rules:</p>
  
  <ul>
  <li><p>A user is given fruit prices and has a chance to buy or sell items in their fruit basket every turn.  </p></li>
  <li><p>The user cannot make more than a 10% total change in their basket on a single turn.  </p></li>
  <li>Fruit prices change every day and when multiplied by the quantities of items in the fruit basket, the total value of the basket changes relative to the fruit price changes every day as well.  </li>
  <li>The program is only given the current price of all the fruits and the current value of the basket (current price of fruit * quantities for all items in the basket).  </li>
  <li>Based on these 2 inputs(all fruit prices and basket total value), the program tries to guess what items are in the basket.  </li>
  <li>A basket cannot hold more than 100 items but slots can be empty  </li>
  <li>The player can play several turns.</li>
  </ul>
  
  <p>My goal is to accurately guess as computationally inexpensively as possible (read: no brute force) and scale if there are thousands of new fruits.</p>
  
  <p>I am struggling to find an answer but in my mind, it’s not hard. If I have the below table.  I could study day 1 and get the following data:</p>
  
  <pre><code>Apple   1
  Pears   2
  Oranges 3
  
  Basket Value = 217
  </code></pre>
  
  <p>I can do a back of napkin calculation and assume, the weights in the basket are: 0 apple, 83 pears, and 17 Oranges equaling a basket value of 217.</p>
  
  <p>The next day, the values of the fruits and basket changes.  To (apple = 2, Pear 3, Oranges 5) with a basket value of 348.   When I take my assumed weights above (0,83,17) I get a total value of 334 – not correct!  Running this by my script, I see the closest match is 0 apples, 76 pears, 24 oranges which although does equal 348 when % change of factored in it’s a 38% change so it’s not possible!</p>
  
  <p>I know I can completely brute force this but if I have 1000 fruits, it won’t scale. Not to jump on any bandwagon but can something like a neural net quickly rule out the unlikely so I calculate large volumes of data? I think they have to be a more scalable/quicker way than pure brute force? Or is there any other type of solution that could get the result?</p>
  
  <p>Here is the raw data (remember program can only see prices and total basket value only):</p>
  
  <p><a href="https://i.stack.imgur.com/MwZYX.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/MwZYX.jpg" alt="enter image description here"></a></p>
  
  <p>Here's some brute force code (Thank you @paul Hankin for a cleaner example than mine):</p>
  
  <pre><code>def possibilities(value, prices):
      for i in range(0, value+1, prices[0]):
          for j in range(0, value+1-i, prices[1]):
              k = value - i - j
              if k % prices[2] == 0:
                  yield i//prices[0], j//prices[1], k//prices[2]
  
  def merge_totals(last, this, r):
      ok = []
      for t in this:
          for l in last:
              f = int(sum(l) * r)
              if all(l[i] -f &lt;= t[i] &lt;= l[i] + f for i in range(len(l))):
                  ok.append(t)
                  break
      return ok
  
  days = [
      (217, (1, 2, 3)),
      (348, (2, 3, 5)),
      (251, (1, 2, 4)),
  ]
  
  ps = None
  for i, d in enumerate(days):
      new_ps = list(possibilities(*d))
      if ps is None:
          ps = new_ps
      ps = merge_totals(ps, new_ps, 0.10)
  
      print('Day %d' % (i+1))
      for p in ps:
          print('Day %d,' % (i+1), 'apples: %s, pears: %s, oranges: %s' % p)
      print
  </code></pre>
  
  <p><strong>Update</strong> - The info so far is awesome. Does it make sense to break the problem into two problems? One is generating the possibilities while the other is finding the relationship between the possibilities(no more than a 10% daily change).  By ruling out possibilities, couldn't that also be used to help only generate possibilities that are possible, to begin with? I'm not sure the approach still but I do feel both problems are different but tightly related. Your thoughts? </p>
  
  <p><strong>Update 2</strong> - there are a lot of questions about the % change.  This is the total volume of items in the basket that can change.  To use the game example, Imagine the store says - you can sell/return/buy fruits but they cannot be more than 10% of your last bill.  So although the change in fruit prices can cause changes in your basket value, the user cannot take any action that would impact it by more than 10%. So if the value was 100, they can make changes that create get it to 110 but not more.</p>