title: Maximum subset sum with two arrays
body: <p>I am not even sure if this can be done in polynomial time. </p>
  
  <p>Problem: </p>
  
  <blockquote>
    <p>Given two arrays of real numbers,</p>
  
  <pre><code>A = (a[1], a[2], ..., a[n]), 
  B = (b[1], b[2], ..., b[n]),  (b[j] &gt; 0, j = 1, 2, ..., n)
  </code></pre>
    
    <p>and a number <code>k</code>, find a subset <code>A'</code> of <code>A (A' = (a[i(1)],
    a[i(2)], ..., a[i(k)]))</code>, which contains exactly <code>k</code> elements, such that, <code>(sum a[i(j)])/(sum b[i(j)])</code> is maximized, where<br><code>j = 1, 2, ..., k</code>.</p>
  </blockquote>
  
  <p>For example, if <code>k == 3</code>, and <code>{a[1], a[5], a[7]}</code> is the result, then</p>
  
  <pre><code>(a[1] + a[5] + a[7])/(b[1] + b[5] + b[7])
  </code></pre>
  
  <p>should be larger than any other combination. Any clue?</p>