#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>

int gr,v[100],sol_max[100],g[100],G,n,nr_sol,c[100],s_max;

int valid(int k) {
	gr = 0;
	for (int i = 1; i <= k; i++)

		gr = gr + v[i] * g[i];
	if (gr <= G)
		return 1;
	else return 0;

}
void optim() {
	int i, s = 0;
	nr_sol++;
	for (i = 1; i <= n; i++)
		s = s + v[i] * c[i];
	if ((nr_sol == 0) || (s > s_max)) {
		s_max = s;
		for (i = 1; i <= n; i++)
			sol_max[i] = v[i];

	}


}
void back(int k) {
	int i;
	for (i = 0; i <= 1; i++) {
		v[k] = i;
		if (valid(k))
			if (k == n) optim();
			else back(k + 1);
	}
}

void citire() {
	int n = 4, G = 20;
	int g[] = { 5, 10, 10 ,5 };
	int c[] = { 5,3,7,2 };
}
void afisare() {
	nr_sol++;
	printf("castigul maxim");
	printf("%d",s_max);
	for (int i = 1; i <= n; i++)
		if (sol_max[i])
			printf("%d %d", g[i], c[i]);
	printf("\n");

}
int main() {
	citire();
	back(1);
	afisare();
	system("pause");
	return 0;
}