/* Umut Öztok  -18.08.08-

Soru: Sınava kadar N tane konu var, her konunun kendine ait bir katkı puanı ve bitirilebilmesi için
gerekli bir zamanı var. Sınava kadar kalan zaman T ise, öğrenci bu sürede hangi konulara çalışarak 
en fazla puanı toplayabilir ?

Çözüm: Dinamik programlama ile çözülebilir. Buna göre; P(i,t), i tane konu ve kalan t zamanda
toplanabilecek en yüksek puanı gösteren fonksiyon olsun.
			
			0    eğer i = 0 ya da t = 0

 P(i,t) =   P(i-1,t) eğer i_zaman > t 

           max([i_puan + P(i-1, t - i_zaman)], [P(i-1,t])

Yukarıdaki formüle göre, i ya da zaman 0 ise alınacak en yüksek puan 0 oluyor. i.konunun çalışma
süresi kalan süreden büyükse, i.konu eklenmiyor ve i-1 konu arasından alınabilecek en yüksek puana 
bakılıyor.Son olarak, i.konunun çalışma süresi kalan süreden az ise, i.konunun eklenip eklenmiyeceği-
ne karar veriliyor. Bu yüzden i.konunun eklenmiş hali ile eklenmemiş halinin puanları karşılaştırı-
lıyor ve en yüksek olan seçiliyor.Eğer i.konu eklenirse en yüksek puan,(i.konunun önem puanı) artı
(i-1 tane konu arasında, t-i.konunun zamanı kadar sürede alınabilecek en yüksek puan) oluyor, aksi
halde (i-1 tane konu arasında, t zamanı kadar sürede alınabilecek en yüksek puana) eşit oluyor.
Böylece, girdiden alınacak değerler ile P(toplam_konu,kalan_süre) hesaplanarak toplanabilecek en yük-
sek puan hesaplanabilir.

En yüksek puanı elde edebilmek için çalışılması gerekli olan konular da P(i,t) fonksiyonu ile öğrenile
bilir. Eğer P(i,t)'nin değeri P(i-1,t)'nin değerinden farklı değilse, bu i.konu en yüksek puanı
elde etmek için kullanılmamış demektir. Aksi halde ise i.konu eklenmiştir, dolayısıyla o konunun adını
bir kenara yazabiliriz. Bundan sonra ise, i.konu eklenmemişse aynı işlemi P(i-1,t) fonksiyonu için
yaparız, şayet i.konu eklenmişse, bu defa aynı işlemi P(i-1, t - i.konunun zamanı) fonksiyonuna uy-
gularız, keza i.konu eklendiği için artık kalan süre t değil, t - i.konunun zamanıdır.

Yukarıda anlatılanların tümünün uygulaması bir adet tablo ile yapılabilir. Bunun için, tamsayı değerleri 
tutan ve girdiden gelen değerlere göre boyutu (toplam konu sayısı+1) X (kalan süre+1) olacak bir 
matris kullanılabilir. Bu matris de, 2 boyutlu dinamik bir dizi ile oluşturulabilir. Dizinin satırları
konuları ve sütunları da kalan zamanları tutacak şekilde ayarlanırsa, Puan[i][t], i tane konu ve 
kalan t zamanda elde edilebilecek en yüksek puanı gösterir, tıpkı P(i,t) fonksiyonu gibi. Dolayısıyla,
Puan[toplam_konu_sayısı][kalan_sure] ile verilecek olan girdiye göre toplanabilecek en yüksek puan
bulunur. Bunu hızlı bir şekilde yapbilmek için de diziyi satır satır doldurmamız gerekir.Daha sonra,
yine yukarıda anlatılan yol izlenerek, hangi konuların eklenmesi gerektiği bulunup, sorunun cevabını 
elde etmiş oluruz.
  
Sonuç olarak, bu algoritma:

O(toplam_konu_sayısı) (girdiden gelen verileri okumak ve bir diziye aktarmak için) +
O(toplam_konu_sayısı X kalan_süre) (P(i,t) değerlerini hesaplayan tabloyu oluşturmak için) +
O(toplam_konu_sayısı) (hangi konulara çalışmak gerektiğini öğrenmek için)

olmak üzere en kötü durumda O(toplam_konu_sayısı X kalan_süre) kadar zaman ve alan gerektirmektedir. 
*/

#include <fstream>
#include <vector>
#include <string>

using namespace std;

struct ders
{
	string ad;
	int zaman;
	int onem;
	ders::ders(string a, int b, int c)
		:ad(a), zaman(b), onem(c) {}
};

void DosyaOku (vector <ders> & a, int & zaman, int & konu)
{
	ifstream girdi;
	girdi.open("sinav.gir");
	int kalan_sure;
	int toplam_konu;

	girdi >> kalan_sure >> toplam_konu;
	
	zaman = kalan_sure;
	konu = toplam_konu;
	
	string isim;
	int sure,puan;
	
	a.push_back(ders("sallama",0,0));// 0. konu, tamamen duygusal...

	for(int k = 0; k < toplam_konu; k++)
	{
		girdi >> isim >> sure >> puan;
		a.push_back(ders(isim, sure, puan));
	}

	girdi.close();
}

void Coz (const vector<ders> & a, int toplam_sure, int toplam_konu)
{
	int **puan;
	puan = new int *[toplam_konu+1];

	int i, t, i_var, i_yok;

	for(i = 0; i < toplam_konu+1; i++)
		puan[i] = new int [toplam_sure+1];

	for(t = 0; t < toplam_sure+1; t++)
		puan[0][t] = 0;
	
	for(i = 1; i < toplam_konu+1; i++)
	{
		puan[i][0] = 0;

		for(t = 1; t < toplam_sure+1; t++)
		{
			i_yok = puan[i-1][t];

			if(a[i].zaman <= t)
			{
				i_var = a[i].onem + puan[i-1][t-a[i].zaman];
				
				if( i_var > i_yok)
				{
					puan[i][t] = i_var;
				}
				else
				{
					puan[i][t] = i_yok;
				}
			}
			else
			{
				puan[i][t] = i_yok;
			}
		}
	}
	
	ofstream cikti;
	cikti.open("sinav.cik");
	
	cikti << puan[toplam_konu][toplam_sure] << endl;

	for(i = toplam_konu, t = toplam_sure ; i > 0 && t > 0; i--)
	{
		if(puan[i][t] != puan[i-1][t])
		{
			cikti << a[i].ad << endl;
			t-= a[i].zaman;
		}
	}

	cikti.close();
}
		
int main()
{
	vector<ders> a;
	int toplam_sure, toplam_konu;

	DosyaOku(a, toplam_sure, toplam_konu);
	Coz(a, toplam_sure, toplam_konu);

	return 0;
}