Cod sursa(job #790291)

Utilizator EduardGeorgescuGeorgescu Eduard EduardGeorgescu Data 20 septembrie 2012 19:48:12
Problema Problema rucsacului Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.38 kb
Raporteaza aceasta sursa 
#include<iostream>
#include<fstream>
using namespace std;

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

int P[5010],W[5010],Best[10010];

int main(){

int N,G,i,j;	
in>>N>>G;

for(i=1;i<=N;i++)
	in>>W[i]>>P[i];

for(i=1;i<=N;i++)
	for(j=G-W[i];j>=0;j--)	
		if(Best[j+W[i]]<Best[j]+P[i])	Best[j+W[i]]=Best[j]+P[i];
	
out<<Best[G];
		
return 0;
}