Cod sursa(job #1786329)
Utilizator | Data | 22 octombrie 2016 19:44:07 | |
---|---|---|---|
Problema | Energii | Scor | 15 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.65 kb |
#include <iostream>
#include <fstream>
#define gmax 1002
#define wmax 5002
using namespace std;
int dp[gmax][wmax],w[gmax],c[gmax],G,W;
int main()
{
ifstream fin ("energii.in");
ofstream fout("energii.out");
fin>>G>>W;
for(int i=1; i<=G; i++)
fin>>w[i]>>c[i];
for(int i=1; i<=G; i++)
{
for(int j=1; j<=W; j++)
{
dp[i][j]=dp[i-1][j];
if(j>=w[i])
dp[i][j]=min(dp[i][j],dp[i-1][j-w[i]]+c[i]);
if(dp[i][j]==0&&j>=w[i])
dp[i][j]=dp[i][j-w[i]]+c[i];
}
}
fout<<dp[G][W];
return 0;
}