#include <bits/stdc++.h>

using namespace std;

struct LopHP {
	char *maLop;
	int soHS;
	int soHSNu;
};

LopHP d[] {
	{"IT6030", 30, 15},
	{"HP6030", 35, 17},
	{"IT6035", 34, 12},
	{"IT1234", 39, 25},
	{"CB5555", 65, 40},
	{"IT5678", 42, 20},
	{"TC1221", 35, 18},
	{"NN9999", 30, 11}
};
int F[1000][1000];
int m = 100;
int n = 7;

void Swap(LopHP &a, LopHP &b) {
	LopHP tmp = a;
	a = b;
	b = tmp;
}

int Quick_Sort(LopHP a[], int left, int right) {
	int pivot = a[(left + right) / 2].soHS;
	int i = left;
	int j = right;
	while (i < j) {
		while (a[i].soHS > pivot) {
			i++;
		}
		while (a[j].soHS < pivot) {
			j--;
		}
		if (i <= j) {
			Swap(a[i], a[j]);
			i++;
			j--;
		}
	}
	if (i < right) {
		Quick_Sort(a, i, right);
	}
	if (left < j) {
		Quick_Sort(a, left, j);
	}
}

int ThamLam(LopHP a[], int m, int n) {
	int i = 0;
	int count = 0;
	while (m > 0 && i <= n) {
		if (m >= a[i].soHS) {
			m -= a[i].soHS;
			count++;
		}
		i++;
	}
	return count;
}

void GhepLop() {
	for (int j = 0; j <= m; j++) F[0][j] = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= m; j++) {
			F[i][j] = F[i - 1][j];
			int temp = F[i - 1][j - d[i].soHS] + d[i].soHSNu;
			if (d[i].soHS <= j && F[i][j] < temp) F[i][j] = temp;
		}
	}
}

void TruyVet() {
	cout << "So HS Nu lon nhat la: " << F[n][m] << endl;
	int i = n; int j = m;
	cout << "Ma lop\tSo HS\tSo HS Nu" << endl;
	while (i != 0) {
		if (F[i][j] != F[i - 1][j]) {
			cout << d[i].maLop << "\t" << d[i].soHS << "\t" << d[i].soHSNu << endl;;
			j = j - d[i].soHS;
		}
		i--;
	}
}

int char_in_string(char T, char *P) {
	int i = 0;
	while (P[i] != '\0') {
		if (P[i] == T) return i;
		i++;
	}
	return -1;
}

int Boyer_Moore_Horspool(char *T, char *P) {
	int dem = 0, i = strlen(P) - 1, v = strlen(P);
	while (i < strlen(T)) {
		int x = v - 1, j = i;
		while (T[j] == P[x] && x > -1) {
			j--; x--;
		}
		if (x < 0) {
			dem++; i = i + v;
		} else {
			x = char_in_string(T[j], P);
			if (x < 0) i = i + v;
			else i = j + v - x - 1;
		}
	}
	return dem;
}

int main() {
	Quick_Sort(d, 0, n);
	for (int i = 0; i <= n; i++) {
		cout << d[i].maLop << "\t" << d[i].soHS << "\t" << d[i].soHSNu << endl;
	}
	cout << "Can it nhat " << ThamLam(d, m, n) << " lop de lay duoc " << m << " HS" << endl;
	
	cout << endl << "Ghep lop gioi han " << m << " hoc sinh" << endl;
	GhepLop();
	TruyVet();
	
	cout << endl << "Cac lop thuoc nganh CNTT la: " << endl;
	for (int i = 0; i <= n; i++) {
		if (Boyer_Moore_Horspool(d[i].maLop, "IT") > 0)
			cout << d[i].maLop << "\t" << d[i].soHS << "\t" << d[i].soHSNu << endl;
	}
	return 0;
}