title: ScubaDiv programming, logical error with outputting
body: <p>This problem is about a Diver or a number of divers which have to take cylinders which contain OXYGEN and NITROGEN inside, also a cylinder has its own weight. Using dynamic programming we have to come up with a solutions which tells the diver the best weight he can get with the desired Oxy and Nitro (to maximaze the time under water for the diver)</p>
  
  <p>The input goes like this:</p>
  
  <pre><code>1          //the number of divers
  5 60       // ox=5 and ni=60 , the amonut of OX and NI the diver needs
  5          //the number of cylinders to choose - n.
  3 36 120   // 1st cyllinder =&gt; ox=3 / nit=36 / weight = 120
  10 25 129  // 2nd cyllinder
  5 50 250   // 3rd cyllinder
  1 45 130   // 4th cyllinder
  4 20 119   // 5th cyllinder
  </code></pre>
  
  <p>And the output here should look like:</p>
  
  <pre><code>249  //the tot weight
  1 2  //cyllinders which were chosen (in this case 1st and 2nd cyllinder)
  </code></pre>
  
  <p>I can find the 249, so the weight but I am struggeling to understand how to get the indexes of the cyllinders, can anyone give me a hint or direct me how can I achive it. Here is the function which calculates the Weight:</p>
  
  <pre><code>int ox,ni,n;
  int o[1000],nit[1000],w[1000];
  
  int best[22][80],next[22][80];
  
  int solve()
      {
          memset(best, 0x3f, sizeof(best));
          best[0][0] = 0;
          for (int k = 0; k &lt; n ;k++)
          {
             memcpy(next,best,sizeof(best));
  
             for (int i = 0; i &lt;= ox ;i++)
             {
                  for (int j = 0 ; j &lt;= ni ;j++)
                  {
                      next[min(ox,i+o[k])][min(ni,j+nit[k])]= min(best[i][j]+w[k], next[min(ox,i+o[k])][min(ni,j+nit[k])]);
                  }
             }
             memcpy(best,next,sizeof(best));
          }
          cout &lt;&lt; endl;
  
          return best[ox][ni];
      }
  </code></pre>
  
  <p>I tried to make if statement like this in the 3rd for loop:</p>
  
  <pre><code>if (((next[min(ox,i+o[k])][min(ni,j+nit[k])]) == (best[i][j]+w[k])) &amp;&amp; ((min(ox, i+o[k]) == ox) || (min(ni, j+nit[k])== ni) )) 
                      {
                          cout &lt;&lt; k &lt;&lt; " ";
                      }
  </code></pre>
  
  <p>But it is not working in most of the cases. Can anyone give me a hint or direct me how to make the statement to catch and print the correct cylinders indexes?</p>
  
  <hr>
  
  <p>The new updated changes:</p>
  
  <pre><code>    #include &lt;stdio.h&gt;
  #include &lt;stdlib.h&gt;
  #include &lt;string.h&gt;
  #include &lt;limits.h&gt;
  #include &lt;iostream&gt;
  
  using namespace std;
  
  typedef struct {    /* typedef for struct containing tank vals */
      int ox,
          nit,
          wt;
  } tank_t;
  
  int main() {
  
      int ndivers = 0,        /* number of divers */
      oxreq = 0,          /* minimum oxygen required */
      nitreq = 0,         /* minimum nitrogen required */
      n = 0,              /* number of cylinders actually read */
      ncyl = 0,           /* number of cylinders from input file */
      wtmin = INT_MAX,    /* minimum weight (initialize to INT_MAX) */
      *indexes = NULL;    /* pointer to track tank indexes */
      tank_t *tanks = NULL, best;   /* pointer to tanks struct */
  
      best.ox = 0;
  
      /* allocate/validate storage for ncyl integers */
      if ((indexes = (int*)calloc(ncyl, sizeof *indexes)) == NULL) {
          perror("calloc-indexes");
          return 1;
      }
  
      /* allocate/validate storage for ncyl tanks */
      if ((tanks = (tank_t*)calloc(ncyl, sizeof *tanks)) == NULL) {
          perror("calloc-tanks");
          return 1;
      }
  
      cin &gt;&gt; ndivers;
  
      for(int i=0; i&lt;ndivers; i++)
      {
          cin &gt;&gt; oxreq &gt;&gt; nitreq;
          cin &gt;&gt; ncyl;
          n = ncyl;
  
          for (int i = 0; i &lt; ncyl; i++)
          {
              cin &gt;&gt; tanks[i].ox &gt;&gt; tanks[i].nit &gt;&gt; tanks[i].wt;
          }
      }
  
  
  
      /* loop over each tank to use as beginning in calc */
      for (int i = 0; i &lt; n; i++) {
          int j = i + 1,      /* set 2nd index as next tank */
              *idx =(int*) calloc(n, sizeof *idx); /* allocate/zero temp index */
                                             /* can move idx alloc out of loop &amp; memset here */
          if (!idx) { /* validate allocation */
              perror("calloc-idx");
              return 1;
          }
          /* use a temp tank_t struct tmp to accumulate values */
          tank_t tmp = { tanks[i].ox, tanks[i].nit, tanks[i].wt };
          idx[i] = 1;                     /* set 1st index value in tmp index */
          while (j &lt; n) {                 /* loop over remaining tanks */
          idx[j] = 1;                 /* set next index as used */
          tmp.ox += tanks[j].ox;      /* add next tank ox */
          tmp.nit += tanks[j].nit;    /* add next tank nit */
          tmp.wt += tanks[j].wt;      /* add next tank wt */
                                          /* check if total ox &amp; nit meet min, &amp; wt &lt; current min */
              if (tmp.ox &gt; oxreq &amp;&amp; tmp.nit &gt; nitreq &amp;&amp; tmp.wt &lt; wtmin) {
                  best = tmp;             /* save ox, nit &amp; wt in best */
                  wtmin = tmp.wt;         /* update minimum wt */
                  memcpy(indexes, idx, n * sizeof *idx); /* copy to indexes */
                  memset(idx, 0, sizeof *idx * n);   /* re-zero idx */
                  memset(&amp;tmp, 0, sizeof tmp);   /* zero tmp tank */
                  idx[i] = 1;                     /* set 1st tank index */
                  tmp.ox = tanks[i].ox;   /* set 1st tank values */
                  tmp.nit = tanks[i].nit;
                  tmp.wt = tanks[i].wt;
              }
              j++;    /* increment 2nd tank counter */
          }
          free(idx); /* free temp index */
      }
      free(tanks);   /* free tanks data - done with it */
  
      cout &lt;&lt; best.wt;
  
      for (int i = 0; i &lt; n; i++)
      {
          if (indexes[i])
              cout &lt;&lt; i + 1 &lt;&lt; " ";
      }
  
      free(indexes); /* free final indexes */
  
      return 0;
  }
  </code></pre>