Cod sursa(job #1494050)
Utilizator | Data | 30 septembrie 2015 16:43:16 | |
---|---|---|---|
Problema | Problema rucsacului | Scor | 10 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.43 kb |
#include<fstream>
using namespace std;
int D[1000][1000],G[1000],P[1000];
int N,Gr;
int main(){
ifstream fin("rucsac.in") ;
ofstream fout("rucsac.out");
fin >> N; fin >> Gr;
for(int i=1;i<=N;i++) fin>> G[i]>>P[i];
for(int i=1;i<=N;i++)
for (int j=1;j<=Gr;j++){
D[i][j]=D[i-1][j];
if(j>=G[i]){
D[i][j]=max(D[i-1][j],D[i-1][j-G[i]]+P[i]);
}
}
fout<<D[N][Gr];
return 0;
}