Cod sursa(job #2493518)
Utilizator | Data | 16 noiembrie 2019 13:30:58 | |
---|---|---|---|
Problema | Problema rucsacului | Scor | 0 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.59 kb |
#include<fstream>
#include<iostream>
using namespace std;
int DP[100][100],W[100],P[100],N,G;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
void citire()
{
fin>>N>>G;
for(int i=1;i<=N;i++)
fin>>W[i]>>P[i];
fin.close();
}
void matrice()
{
for(int i=1;i<=N;i++)
for(int j=0;j<=G;j++)
{
if(j-W[i]>=0)
DP[i][j]=max(DP[i-1][j],DP[i-1][j-W[i]]+P[i]);
else
DP[i][j]=DP[i-1][j];
}
}
int main()
{
citire();
matrice();
fout<<DP[N][G];
return 0;
}