Cod sursa(job #894655)

Utilizator Daniel_BotBot Cristian Daniel Daniel_Bot Data 26 februarie 2013 22:41:44
Problema Energii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <iostream>
#include <fstream>
#define MAX 1<<20
using namespace std;
int n,W;
int E[1001],C[1001],solutie[5001];

int rezolvaFolosindProgramareDinamica()
{
    for(int i=1;i<=n;i++)
        for(int j=W;j>=0;--j)
            if(j>E[i]) // daca am destula energie pentru a porni generatorul i
            {
                if(solutie[j-E[i]] + C[i] < solutie[j])
                    solutie[j] = solutie[j-E[i]] + C[i] ;
            }
            else
            {
                if(solutie[j]>C[i])
                    solutie[j]=C[i];
            }

    if (solutie[W] == MAX)
        return -1;
    else return solutie[W];
}

int main()
{
    ifstream in("energii.in");
    in>>n>>W;
    for(int i=1;i<=n;++i)
        in>>E[i]>>C[i];
    for(int i=1;i<=W;i++)
        solutie[i]= MAX;
    in.close();
    ofstream out("energii.out");
    out<<rezolvaFolosindProgramareDinamica();
    out.close();
    return 0;
}