title: Which machine learning algorithm to evaluate the best combinations of groups?
body: <p>Here's a simplified version of the problem:</p>
  
  <blockquote>
    <p>You have a group of five warriors. Each warrior owns between 1 and 10 items, and each can bring 1 of their items to a battle. Given information about the battle (terrain type, time of day, etc.), which weapon should each warrior choose to produce the strongest group?</p>
  </blockquote>
  
  <p>Items can be a bow, shield, sword, catapult, medical kit, horse, etc. Terrain type can be mountainous, plains, marsh, snow, etc.</p>
  
  <p>Note that the rules cannot be easily codified because they're based on synergies between items and and terrain conditions: for instance, a "sword" is a good weapon, and a "bow" is a good weapon, but five warriors with swords or five warriors with bows is worse than two warriors with bows and three with swords, because five warriors with swords are vulnerable to ranged attacks without cover, and five warriors with bows are rendered useless by shields. There are also complex terrain conditions, for example if the terrain is very difficult to cross or if you're on top of a hill, bows are better. A horse would be great on flat terrain, but if one person has a horse and the other people don't have weapons then the horse is useless.</p>
  
  <p>My naive solution is to (a) train a machine learning regression algorithm to take terrain information and a set of 5 item combinations as input and produce a value, where higher is better, and then (b) produce all combinatoric inputs of items, feed each into the algorithm, and pick the highest value. However, that gets prohibitively expensive every quickly as the combinatorics explode.</p>
  
  <p>Is there a better algorithm for saying "given all of these possibilities, pick the best combination"? Bonus points if it's usable on Amazon's Machine Learning stack.</p>