Want more features on Pastebin? Sign Up, it's FREE!
Guest

problema rucsacului

By: a guest on Dec 9th, 2011  |  syntax: C++  |  size: 1.20 KB  |  views: 313  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. // Problema rucsacului 1/0 (nu pot fi luate bucati dintr-un obiect)
  2. // Rezolvare prin programare dinamica
  3. // date.in
  4. // 5 10
  5. //
  6. // 3 6
  7. // 2 3
  8. // 5 20
  9. // 1 7
  10. // 7 23
  11.  
  12. #include "stdafx.h"
  13. #include <iostream>
  14. #include <fstream>
  15. #include <iomanip>
  16. using namespace std;
  17.  
  18. void date_in();
  19. void date_out();
  20.  
  21. int n, c, sol[50][50];
  22.  
  23. struct ob
  24. {
  25.         int g, v;
  26. }X[20];
  27.  
  28. int main()
  29. {
  30.         int i, j;
  31.        
  32.         date_in();
  33.         for(i = 1; i <= n; i++)
  34.                 for(j = 1; j <= c; j++)
  35.                 {
  36.                         if(X[i].g > j)
  37.                                 sol[i][j] = sol[i-1][j];
  38.  
  39.                         else if(X[i].g == j)
  40.                         {
  41.                                 if(sol[i-1][j] < X[i].v)
  42.                                         sol[i][j] = X[i].v;
  43.                                 else
  44.                                         sol[i][j] = sol[i-1][j];
  45.                         }
  46.                        
  47.                         else
  48.                         {
  49.                                 if(sol[i-1][j-X[i].g])
  50.                                 {      
  51.                                         if(sol[i-1][j-X[i].g] + X[i].v > sol[i-1][j])
  52.                                                 sol[i][j] = sol[i-1][j-X[i].g] + X[i].v;
  53.                                         else
  54.                                                 sol[i][j] = sol[i-1][j];
  55.                                 }
  56.                                 else
  57.                                         sol[i][j] = sol[i-1][j];
  58.                         }
  59.                 }
  60.                
  61.         date_out();
  62.         return 0;
  63. }
  64.  
  65. void date_in()
  66. {
  67.         ifstream in("date.in");
  68.         in >> n >> c;
  69.         for(int i = 0; i < n; i++)
  70.                 in >> X[i].g >> X[i].v;
  71. }
  72.  
  73. void date_out()
  74. {
  75.         for(int i = 1; i <= n; i++)
  76.         {
  77.                 for(int j = 1; j <= c; j++)
  78.                         cout << setw(3) << sol[i][j];
  79.                 cout << "\n";
  80.         }
  81. }
  82.  
  83.  
clone this paste RAW Paste Data