Cod sursa(job #2030713)
Utilizator | Data | 2 octombrie 2017 00:01:10 | |
---|---|---|---|
Problema | Problema rucsacului | Scor | 35 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.52 kb |
#include <fstream>
using namespace std;
ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");
short n,i,G,w[5001],p[5001],j;
int maxim,a[5001][10001];
int main(){
fin>>n>>G;
for(i=1;i<=n;i++){
fin>>w[i]>>p[i];
}
for(i=1;i<=n;i++)
for(j=1;j<=G;j++){
if(w[i]>j)
a[i][j]=a[i-1][j];
else
a[i][j]=max(a[i-1][j],a[i-1][j-w[i]]+p[i]);
if(a[i][j]>maxim)
maxim=a[i][j];
}
fout<<maxim;
}