Cod sursa(job #643409)

Utilizator mihaibogdan10Mihai Bogdan mihaibogdan10 Data 3 decembrie 2011 17:36:19
Problema Problema rucsacului Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include<cstdio>
#define max(a,b) a > b ? a : b 
using namespace std;

int main(){
	freopen("rucsac.in", "r", stdin), freopen("rucsac.out", "w", stdout);
	int nrOb, grMax, i, j, gr, profit;
	scanf ("%d %d", &nrOb, &grMax);
	int lin1[grMax+1], lin2[grMax+1], *l1 = lin1, *l2 = lin2, *aux;
	
	for (i = 0 ; i <= grMax; i++) lin1[i] = lin2[i] = 0;
	for (i = 0; i < nrOb; i++){
		scanf ("%d %d", &gr, &profit);
		for (j = gr; j <= grMax; j++)
			l2[j] = max(l1[j - gr] + profit, l1[j]);
		aux = l1, l1 = l2, l2 = aux;
	}
	
	profit = - 0xfffffff;
	for (j = 1; j <= grMax; j++)
		if (profit < *&l1[j]) profit = *&l1[j];
	printf("%d\n", profit);
		
	return 0;
}