#include <iostream>
#include <iomanip>
using namespace std;
int **utworzTabele(int W, int n)
{
  int** tab = new int*[n];
  for(int i = 0; i < n; i++)
  {
    tab[i] = new int[W];
    for(int j = 0; j < W; j++)
      tab[i][j] = 10000;
  }
  for (int i = 0; i < n; i++)
      tab[i][0] = 0;
  return tab;
}

void usunTabele(int **tab, int n)
{
      for(int i = 0; i < n; i++)
        delete[] tab[i];
      delete[] tab;
}

int main()
{
    int n, *w, *p, W, i, j;
    cout << "Podaj liczbe naminalow: ";
    cin >> n;
    cout << "Podaj kwote do wydania: ";
    cin >> W;
    w = new int[n+1];
    cout << "Podaj kolejne nominaly:" << endl;
    for(i = 1; i <= n; i++)
        cin >> w[i];

    int **P = utworzTabele(W+1, n+1);
    int **Q = utworzTabele(W+1, n+1);

    for(i = 1; i <= n; i++)
        for(j = 1; j <= W; j++)
          if((w[i] <= j) && (P[i-1][j] >= P[i][j-w[i]] + 1))
          {
              P[i][j] = P[i][j-w[i]] + 1;
              Q[i][j] = w[i];
          }
          else
          {
              P[i][j] = P[i-1][j];
              Q[i][j] = Q[i-1][j];
          }

    for(i=1;i<=n;i++){
            for(j=0;j<=W;j++)
             cout << setw(2) << P[i][j] << " ";
      cout << endl;
    }
    cout << endl << endl;
    for(i=1;i<=n;i++){
            for(j=0;j<=W;j++)
             cout << setw(2) << Q[i][j] << " ";
      cout << endl;
    }
    cout<<"Najmniejsza liczba monet: "<<P[n][W]<<endl;
    cout<<"Wartosci monet:"<<endl;
    i = n;
    j = W;
    while(W != 0)
    {
        cout << Q[i][j] << "  ";
        W = W - Q[i][j];
        j = j - Q[i][j];
    }

    usunTabele(P, n);
    usunTabele(Q, n);
    delete []w;
    delete []p;

    return 0;
}