Cod sursa(job #2148831)
| Utilizator | Data | 2 martie 2018 04:58:57 | |
|---|---|---|---|
| Problema | Problema rucsacului | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.66 kb |
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
const int NMAX = 5002;
const int GMAX = 10002;
int n,s;
int p[NMAX],w[NMAX],sol[GMAX];
int ans=0;
void read()
{
in>>n>>s;
for(int i=1;i<=n;i++)
{
in>>w[i]>>p[i];
}
}
void solve()
{
for(int i=1;i<=n;i++)
{
for(int j=s-w[i];j>=0;j--)
{
if(sol[j]+p[i]>sol[w[i]+j])
{
sol[w[i]+j]=sol[j]+p[i];
ans=max(ans,sol[w[i]+j]);
}
}
}
}
int main()
{
read();
solve();
out<<ans;
}
