Cod sursa(job #649472)

Utilizator toniobFMI - Barbalau Antonio toniob Data 16 decembrie 2011 10:45:09
Problema Problema rucsacului Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <fstream>
using namespace std;

ifstream in ("rucsac.in");
ofstream out ("rucsac.out");

struct obiect {
	int g, p;
}items[5001];
int n,g,p[10002];

inline int max (int a,int b){
	return a > b ? a : b;
}

void citire () {
	in >> n >> g;
	for (int i = 1; i <= g; ++i) {
		p[i] = -1;
	}
	p[0]=0;
}

void pd () {
	int e;
	for (int i = 1; i <= n; ++i) {
		in >> items[i].g >> items[i].p;
		for (int j = g; j >= 0; --j) {
			if (p[j] == -1){
				continue;
			}
			e = j + items[i].g;
			if (e > g) {
				continue;
			}
			if (p[e] < p[j] + items[i].p){
				p[e]=p[j] + items[i].p;
			}
		}
	}
}

void afisare(){
	for (int i = g; i >= 1; --i) {
		if (p[g] != -1) {
			out << p[g] << '\n';
			return;
		}
	}
}

int main () {
	citire ();
	
	pd();
	
	afisare();
	
	return 0;
}