Cod sursa(job #2799378)
Utilizator | Brindea Robert Robert.Brindea | Data | 13 noiembrie 2021 09:35:41 |
---|---|---|---|
Problema | Energii | Scor | 95 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 0.58 kb |
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("energii.in");
ofstream fout("energii.out");
const int MAXN = 10004;
int n, w, energie[MAXN], cost[MAXN], dp[5005];
int main()
{
fin >> n >> w;
for(int i = 1; i <= n; i++)
fin >> energie[i] >> cost[i];
for(int i = 0; i <= 5001; i++) dp[i] = 10005;
for(int i = 1; i <= n; i++)
for(int j = w; j; j--)
if(j <= energie[i]) dp[j] = min(dp[j], cost[i]);
else dp[j] = min(dp[j], dp[j-energie[i]] + cost[i]);
fout << dp[w];
return 0;
}