Cod sursa(job #2852910)
| Utilizator | Data | 19 februarie 2022 18:05:11 | |
|---|---|---|---|
| Problema | Problema rucsacului | Scor | 85 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 0.67 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
const int N=5005,G=1e4+5;
int dp[G],p[N],w[N];
void Afisare(int n)
{
for(int i=1;i<=n;i++)
cout<<dp[i]<<' ';
cout<<'\n';
}
int main()
{
int n,g;
in>>n>>g;
for(int i=1;i<=n;i++)
in>>w[i]>>p[i];
int wMAX=0;
for(int i=1;i<=n;i++)
{
for(int j=wMAX;j>=0;j--)
if(j+w[i]<=g && dp[j]+p[i] > dp[j+w[i]])
{
if(j+w[i]>wMAX) wMAX=j+w[i];
dp[j+w[i]]=dp[j]+p[i];
}
//Afisare(g);
}
out<<dp[g];
return 0;
}
