Cod sursa(job #2218795)
| Utilizator | Data | 5 iulie 2018 20:02:15 | |
|---|---|---|---|
| Problema | Problema rucsacului | Scor | 25 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.52 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int N,G,W[5001],P[5001],K[5001][10001];
int main()
{
fin >> N >> G;
for(int i=0;i<N;i++)
fin >> W[i] >> P[i];
for(int i=0;i<=N;i++)
for(int j=0;j<=G;j++)
{
if(i==0 or j==0)
K[i][j]=0;
else if(W[i-1]<=j)
K[i][j]=max(P[i-1]+K[i-1][j-W[i-1]],K[i-1][j]);
else
K[i][j]=K[i-1][j];
}
fout << K[N][G];
return 0;
}
