#include<iostream>
#include<vector>
#include <algorithm>

struct obiekt
{
  int waga;
  int wartosc;
  std::string nazwa;
};

std::vector <obiekt> vec;

  void Bellman(obiekt* pierw, int n, int udzwig)
  {
      int wartosc[udzwig+1][n];
      int cowloz[udzwig+1][n];

      for(int i = 1; i < n; i++)
      {
        for(int i2=1; i2<=udzwig; i2++)
        {
          if(i2 >= pierw[i].waga && wartosc[i-1][i2] < wartosc[i][i2-pierw[i].waga] + pierw[i].wartosc)
          {
            wartosc[i][i2] = wartosc[i][i2 - pierw[i].waga] + pierw[i].wartosc;
            cowloz[i][i2] = (i+1);
          }

          else
          {
            wartosc[i][i2] = wartosc[i-1][i2];
            cowloz[i][i2] = cowloz[i-1][i2];
          }
        }
      }
      int udz2 = udzwig;

  	do
  	{
		vec.push_back(pierw[cowloz[n-1][udz2]]);
		udz2 -= pierw[cowloz[n-1][udz2]].waga;
	  } while(udz2>0);

    int w = wartosc[n-1][udzwig];
}


int main()
{

  int n; int udzwig;

  std::cout<<"\nWpisz udzwig plecaka:  ";
  std::cin>>udzwig;

  std::cout<<"\nWpisz ilosc przedmiotow na liscie:  ";
  std::cin>>n;

  obiekt tab[n];

  for(int i=0; i<n; ++i)
  {
    std::cout<<"\n\n\nWpisz nazwe przedmiotu:  ";
    std::cin>>tab[i].nazwa;
    std::cout<<"Wpisz wartosc przedmiotu:  ";
    std::cin>>tab[i].wartosc;
    std::cout<<"Wpisz wage przedmiotu:  ";
    std::cin>>tab[i].waga;
  }

  Bellman(tab, n, udzwig);

  std::cout<<"Do plecaka włożone zostaną: ";
  for(int i=0; i<vec.size(); ++i)
  {
    if(i==vec.size()-1) {std::cout<<vec[i].nazwa<<'.'; return 0;}

    std::cout<<vec[i].nazwa<<','<<' ';
  }
}