title: How can I improve this algorithm for solving a modified Postage Stamp puzzle?
body: <p><a href="http://azspcs.net/Contest/SonOfDarts" rel="nofollow noreferrer"><strong>Son of Darts Problem</strong></a> was a contest on <a href="http://azspcs.net/" rel="nofollow noreferrer">Al Zimmermann's Programming Contests</a> that ended on 20 Jun 2010 :</p>
  
  <blockquote>
    <ul>
    <li><p>Suppose that you have a dartboard that is divided into R regions. Each dartboard region has a positive integer value associated with it. Further suppose that you have D darts and that you throw each of them at the dartboard. Each dart either lands in one of the board's R regions or misses the board altogether. Your score is the sum of the values for the regions in which the darts land. A dart that misses the board contributes nothing to your score. If multiple darts land in the same region, you accumulate the value for that region multiple times.</p></li>
    <li><p>For example, suppose that R = 5, that the dartboard regions have values (1, 2, 4, 7, 11), and that D = 3. If your three darts land in regions 2, 4 and 11 you score 17 points. If one dart misses the board and the other two land in region 7 you score 14 points.</p></li>
    <li><p>The Darts Problem is this: for a given R and D, determine what values should be associated with a dartboard's R regions in order to maximize the smallest score unattainable by throwing D darts.</p>
  
  <pre><code>D = number of darts    R = number of dartboard regions
      3                      1 through 40
      4                      1 through 30
      5                      1 through 20
      6                      1 through 10
  </code></pre></li>
    </ul>
  </blockquote>
  
  <p>==================================================================================</p>
  
  <p>BASIC ALGORITHM USED (explained for <code>D = 3</code>)</p>
  
  <ul>
  <li><p>I start with the <strong>result</strong> array shown below. <strong>0</strong> and <strong>1</strong> are the scores that should be there on the regions of the dartboard. <strong>0</strong> indicates that the dart missed the board. So, I am going to generate this array for 41 elements (one extra to compensate for <strong>0</strong>). <strong>1</strong> is compulsary because otherwise there is no other way to generate <strong>1</strong>.</p>
  
  <pre><code> ____ ____ 
  |    |    |
  |  0 |  1 |
  |____|____|
  </code></pre></li>
  <li><p>I generate the <strong>scratch</strong> array which shows what all totals are achievable using the dart scores in the result array, in three throws. The elements underlined are the ones that were used to generate the <strong>scratch</strong>.</p>
  
  <pre><code>0 = 0 + 0 + 0
  1 = 1 + 0 + 0
  2 = 1 + 1 + 0
  3 = 1 + 1 + 1
   ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____
  | *  | *  | *  | *  |    |    |    |    |    |    |    |    |    |
  |  0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9 | 10 | 11 | 12 |
  |__-_|__-_|____|____|____|____|____|____|____|____|____|____|____|
  </code></pre></li>
  <li><p>Now the candidates for the next element in the result array are <strong>2</strong>, <strong>3</strong> or <strong>4</strong>.</p>
  
  <ul>
  <li><p><strong>2</strong> = element one greater than the current largest element</p></li>
  <li><p><strong>4</strong> = the smallent unachievable element</p></li>
  </ul></li>
  <li><p>I try each of these candidates in turn and see that which is the maximum of smallest unachievable elements in each case.
   For example</p>
  
  <p>(0, 1, <strong>2</strong>)</p>
  
  <pre><code> ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ 
  | *  | *  | *  | *  | *  | *  | *  |    |    |    |    |    |    |
  |  0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9 | 10 | 11 | 12 |
  |__-_|__-_|__-_|____|____|____|____|____|____|____|____|____|____|
  </code></pre>
  
  <p>(0, 1, <strong>3</strong>)</p>
  
  <pre><code> ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ 
  | *  | *  | *  | *  | *  | *  | *  | *  |    | *  |    |    |    |
  |  0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9 | 10 | 11 | 12 |
  |__-_|__-_|____|__-_|____|____|____|____|____|____|____|____|____|
  </code></pre>
  
  <p>(0, 1, <strong>4</strong>)</p>
  
  <pre><code> ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ 
  | *  | *  | *  | *  | *  | *  | *  |    | *  | *  |    |    | *  |
  |  0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9 | 10 | 11 | 12 |
  |__-_|__-_|____|____|__-_|____|____|____|____|____|____|____|____|
  </code></pre></li>
  <li><p><code>max (7, 8, 7) = 8</code>. So, <strong>3</strong> is chosen as the next element.</p></li>
  <li><p>If suppose there was a tie, for example, if I had to choose between (0, 1, <strong>2</strong>) and (0, 1, <strong>4</strong>), to break the tie I would count the number of achievable numbers which is more in case of (0, 1, <strong>4</strong>). So, I would choose (0, 1, <strong>4</strong>) over (0, 1, <strong>2</strong>).</p></li>
  <li><p>But in this case, (0, 1, <strong>3</strong>) is the winner and the result set looks like below. Then, I repeat the steps until I have 41 elements.</p>
  
  <pre><code> ____ ____ ____
  |    |    |    |
  |  0 |  1 |  3 |
  |____|____|____|
  </code></pre></li>
  <li><p>The algorithm is greedy in the sense that it assumes that (solution for R = 20) is a subset of (solution for R = 30). So, I do not calculate results for each value of R, but I do calculate results for each value of D. So, for D = 3, I cauculate result for R = 40 and then take the first 30 elements of the result for R = 30, for example.</p></li>
  <li><p>The algorithm is greedy in the sense that it assumes that the target at each step (in creating the <strong>result</strong> array) is to achieve the minimum unachievable total at the stage.</p></li>
  <li><p>To be able to perform better than brute force, the algorithm eliminates some candidates for the result array. For example, in the case depicted in the diagram below (for a (0, 1, 4) <strong>result</strong> array), I only consider 5, 6 and 7 as candidates for the next element and exclude 2 and 3 though they are still not used. This assumption might give me suboptimal results in some cases, but it does cut down on a lot of calculation when <strong>scratch</strong> grows to thousands of elements.</p>
  
  <pre><code> ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ ____ 
  | *  | *  | *  | *  | *  | *  | *  |    | *  | *  |    |    | *  |
  |  0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9 | 10 | 11 | 12 |
  |__-_|__-_|____|____|__-_|____|____|____|____|____|____|____|____|
  </code></pre></li>
  </ul>
  
  <p>IMPROVEMENTS TO THE ALGORITHM</p>
  
  <ul>
  <li><p>Since this was not giving too good results, I tried generating sets of results for each value of D. For example, instead of choosing the best next element for <strong>result</strong>, I could also choose the second best or the third best element. So, for 39 steps to go (to 41 elements in result), I could generate around 3^39 (for each choice, I can have either the best or the second best or the third best element) cases which is too many. So, I decided to go with atmost one second best and atmost one third best choices. That reduced the number of cases to around <sup>40</sup>C<sub>1</sub> * <sup>39</sup>C<sub>1</sub> = 577980 results. Any more than this would lead to HUGE number of cases for higher values of R (for higher values of D).</p></li>
  <li><p>Out of these ~6E5 results that I have, I calculate the minimum unachievable element for each value of R from 1 to 40. So, each of the R values gets to choose the best from these 6E5 values.</p></li>
  </ul>
  
  <p>PROBLEMS</p>
  
  <ul>
  <li><p>This algorithm does not produce the best <strong>result</strong> sets, or even close.</p></li>
  <li><p>I even went to fourth and fifth best choices for D = 3, and they did not give any major improvements in the results. So, I did not know where I should tune my algorithm.</p></li>
  </ul>
  
  <blockquote>
    <p><strong>Where all can I tune this algorithm to get better results?</strong></p>
    
    <p>Are there any obvious mistakes that the algorithm makes?</p>
  </blockquote>
  
  <p>Any comments/suggestions are welcome.</p>
  
  <p><sub>There was another question on the same topic <a href="https://stackoverflow.com/questions/2627225/al-zimmermanns-son-of-darts">here</a>. I am more interested in knowing where my algorithm can be improved.</sub></p>