title: Helping to solve program knapsack the dynamic programming method
body: <p>Friends who can program "knapsack the dynamic programming method" and "C ++" Will share with me?<br><br>
  Algorithm to solve knapsack with dynamic programming:
  <img src="https://i.stack.imgur.com/Gn0hU.png" alt="enter image description here">
  Thank You all</p>
  
  <p>Code to the method of "weight / value" :</p>
  
  <pre><code>#include &lt;conio.h&gt;
  #include &lt;stdio.h&gt;
  #include &lt;iostream&gt;
  #include &lt;windows.h&gt;
  using namespace std;
  void gotoxy(int x, int y)
  {
      COORD pos;
      HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE);
  
      if (INVALID_HANDLE_VALUE != hConsole)
      {
          pos.X = x;
          pos.Y = y;
  
          SetConsoleCursorPosition(hConsole, pos);
      }
  }
  
  int wherey()
  {
      CONSOLE_SCREEN_BUFFER_INFO csbi;
      COORD                      result;
      if (!GetConsoleScreenBufferInfo(GetStdHandle(STD_OUTPUT_HANDLE), &amp;csbi))
          return -1;
      result = csbi.dwCursorPosition;
      return result.Y;
  }
  
  int wherex()
  {
      CONSOLE_SCREEN_BUFFER_INFO csbi;
      COORD                      result;
      if (!GetConsoleScreenBufferInfo(GetStdHandle(STD_OUTPUT_HANDLE), &amp;csbi))
          return -1;
      result = csbi.dwCursorPosition;
      return result.X;
  }
  
  void sortbypw(int p[], int w[], int n)
  {
      int i, t, j;
      for (i = 0; i &lt;= n - 1; i++)
          for (j = i + 1; j &lt;= n; j++)
              if (((float)p[i] / w[i])&lt;((float)p[j] / w[j]))
              {
          t = p[i];
          p[i] = p[j];
          p[j] = t;
          t = w[i];
          w[i] = w[j];
          w[j] = t;
      }
  }
  
  float knapsack(int p[], int w[], int n, int m)
  {
      sortbypw(p, w, n);
      int w1 = m;
      int i = 0;
      float pp = 0;
      while (i &lt;= n &amp;&amp; w1&gt;0)
      {
          if (w[i]&lt;w1)
          {
              cout &lt;&lt; " p : " &lt;&lt; p[i];
              w1 -= w[i];
              pp += p[i];
              i++;
          }
          else
          {
              cout &lt;&lt; " p : " &lt;&lt; p[i];
              pp += w1*((float)p[i] / w[i]);
              w1 = 0;
          }
      }
      return pp;
  }
  
  void main()
  {
      // Ali Aghajani 2015/06/07
      int p[100] = { 6, 12, 7, 18, 9, 30 };
      int w[100] = { 1, 5, 3, 9, 5, 20 };
      system("cls");
      cout &lt;&lt; "If You Want Input Data Press (Y) Else Press (N) :";
      char ch = cin.get();
      if (ch == 'n')
          cout &lt;&lt; "\n\n Arzesh Knapsack : " &lt;&lt; knapsack(p, w, 5, 20);
      else
      {
          int n, m;
          cout &lt;&lt; "\nEnter Weight Knapsack : ";
          cin &gt;&gt; m;
          cout &lt;&lt; "Enter Num : ";
          cin &gt;&gt; n;
          for (int i = 0; i&lt;n; i++)
          {
              cout &lt;&lt; "Enter Arzesh : ";
              cin &gt;&gt; p[i];
              cout &lt;&lt; "\nEnter Weight : ";
              cin &gt;&gt; w[i];
              gotoxy(20, wherey() - 2);
              cout &lt;&lt; " P/W Is : " &lt;&lt; (float)p[i] / w[i];
              gotoxy(1, wherey() + 2);
              cout &lt;&lt; ".......................................\n";
          }
          cout &lt;&lt; "\n\n Arzesh Knapsack : " &lt;&lt; knapsack(p, w, n - 1, m);
      }
  }
  </code></pre>