title: Finding subsets of items with non-conflicting categories
body: <p>I have a list of objects with each Item having a cost and a set of resources associated with it (see below). I'm looking for a way to select a subset from this list based on the combined cost and each resource must be contained at most once (not every resource has to be included though). The way the subset's combined cost is calculated should be exchangeable (e.g. max, min, avg). If two subsets have the same combined cost the subset with more items is selected.</p>
  
  <pre><code> Item  |  cost   resources [1..3]
   ================================
    P1   |  0.5          B
    P2   |   4         A B C
    P3   |  1.5        A B
    P4   |   2             C
    P5   |   2         A
  </code></pre>
  
  <p>This would allow for these combinations:</p>
  
  <pre><code> Variant  |   Items    sum
   ==========================
      V1    |  P1 P4 P5  4.5
      V2    |     P2      4
      V3    |   P3 P4    3.5
  </code></pre>
  
  <p>For a maximum selection V1 would be selected. The number of items can span from anywhere between 1 and a few dozen, the same is true for the number of resources.</p>
  
  <p>My brute force approach would just sum up the cost of all possible permutations and select the max/min one, but I assume there is a much more efficient way to do this. I'm coding in Java 8 but I'm fine with pseudocode or Matlab.</p>
  
  <p>I found some questions which appeared to be similar (i.e. <a href="https://stackoverflow.com/questions/19316135/find-a-deterministic-best-choice-of-non-conflicting-subset">(1)</a>, <a href="https://stackoverflow.com/questions/8800226/algorithm-to-find-the-best-combination-of-items-under-certain-constraints?rq=1">(2)</a>, <a href="https://stackoverflow.com/questions/1378098/finding-all-non-conflicting-combinations-of-values-from-multiple-lists-of-values">(3)</a>) but I couldn't quite transfer them to my problem, so forgive me if you think this is a duplicate :/</p>
  
  <p>Thanks in advance!
  ~</p>
  
  <p><strong>Clarification</strong></p>
  
  <p>A friend of mine was confused about what kinds of sets I want. No matter how I select my subset in the end, I always want to generate subsets with as many items in them as possible. If I have added P3 to my subset and can add P4 without creating a conflict (that is, a resource is used twice within the subset) then I want P3+P4, not just P3.</p>
  
  <p><strong>Clarification2</strong></p>
  
  <p>"Variants don't have to contain all resources" means that if it's impossible to add an item to fill in a missing resource slot without creating a conflict (because all items with the missing resource also have another resource already present) then the subset is complete.</p>