daily pastebin goal
30%
SHARE
TWEET

Untitled

a guest Mar 22nd, 2019 60 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <iomanip>
  3. using namespace std;
  4. int **utworzTabele(int W, int n)
  5. {
  6.   int** tab = new int*[n];
  7.   for(int i = 0; i < n; i++)
  8.   {
  9.     tab[i] = new int[W];
  10.     for(int j = 0; j < W; j++)
  11.       tab[i][j] = 10000;
  12.   }
  13.   for (int i = 0; i < n; i++)
  14.       tab[i][0] = 0;
  15.   return tab;
  16. }
  17.  
  18. void usunTabele(int **tab, int n)
  19. {
  20.       for(int i = 0; i < n; i++)
  21.         delete[] tab[i];
  22.       delete[] tab;
  23. }
  24.  
  25. int main()
  26. {
  27.     int n, *w, *p, W, i, j;
  28.     cout << "Podaj liczbe naminalow: ";
  29.     cin >> n;
  30.     cout << "Podaj kwote do wydania: ";
  31.     cin >> W;
  32.     w = new int[n+1];
  33.     cout << "Podaj kolejne nominaly:" << endl;
  34.     for(i = 1; i <= n; i++)
  35.         cin >> w[i];
  36.  
  37.     int **P = utworzTabele(W+1, n+1);
  38.     int **Q = utworzTabele(W+1, n+1);
  39.  
  40.     for(i = 1; i <= n; i++)
  41.         for(j = 1; j <= W; j++)
  42.           if((w[i] <= j) && (P[i-1][j] >= P[i][j-w[i]] + 1))
  43.           {
  44.               P[i][j] = P[i][j-w[i]] + 1;
  45.               Q[i][j] = w[i];
  46.           }
  47.           else
  48.           {
  49.               P[i][j] = P[i-1][j];
  50.               Q[i][j] = Q[i-1][j];
  51.           }
  52.  
  53.     for(i=1;i<=n;i++){
  54.             for(j=0;j<=W;j++)
  55.              cout << setw(2) << P[i][j] << " ";
  56.       cout << endl;
  57.     }
  58.     cout << endl << endl;
  59.     for(i=1;i<=n;i++){
  60.             for(j=0;j<=W;j++)
  61.              cout << setw(2) << Q[i][j] << " ";
  62.       cout << endl;
  63.     }
  64.     cout<<"Najmniejsza liczba monet: "<<P[n][W]<<endl;
  65.     cout<<"Wartosci monet:"<<endl;
  66.     i = n;
  67.     j = W;
  68.     while(W != 0)
  69.     {
  70.         cout << Q[i][j] << "  ";
  71.         W = W - Q[i][j];
  72.         j = j - Q[i][j];
  73.     }
  74.  
  75.     usunTabele(P, n);
  76.     usunTabele(Q, n);
  77.     delete []w;
  78.     delete []p;
  79.  
  80.     return 0;
  81. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top