Cod sursa(job #884944)

Utilizator Daniel_BotBot Cristian Daniel Daniel_Bot Data 21 februarie 2013 15:04:35
Problema Energii Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <iostream>
#include <fstream>
using namespace std;
/* n-nr de obiecte, W-costul necesar repornirii centralei; V-matricea in care calculez costul */
int i,j,MAX=0,n,V[1001][10001],W;
int d[10001],p[10001],sol[10001];

enum{marcat=1,nemarcat=0};

void calculeazaCost()
{
    //initializez matricea
    for(j=0;j<=MAX;j++)
        V[0][j]=0;
    for(i=1;i<=n;i++)
        for(j=0;j<=MAX;j++)
            if(d[i]>j)
                V[i][j]=V[i-1][j];
            else
                V[i][j]= V[i-1][j] > (V[i-1][j-d[i]] + p[i]) ? V[i-1][j] : (V[i-1][j-d[i]] + p[i]);
}

void aflareGeneratoare()
{
    i=n;
    j=MAX;
    while(i>0 && j>0)
    {
        if(V[i][j]==V[i-1][j])
            i--;
        else{
            sol[i]=marcat;
            j-=d[i];
            i--;
        }
    }
}

int main()
{
    ifstream in("energii.in");
    ofstream out("energii.out");
    in>>n>>W;
    for(i=1;i<=n;i++)
    {
        in>>d[i]>>p[i];
        if(MAX<d[i])
            MAX=d[i];
    }
    calculeazaCost();
    aflareGeneratoare();
    MAX=0;
    for(i=0;i<=n;i++)
        if(sol[i]==marcat)
            MAX+=p[i];
    if(MAX>=W)
        out<<MAX;
    else
        out<<"-1";
    return 0;
}