Cod sursa(job #819538)

Utilizator CataBBaincescu Catalina CataB Data 19 noiembrie 2012 11:20:08
Problema Problema rucsacului Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <fstream>

using namespace std;

ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");

void citire();
void pd();
void afisare();

int n, w[5001], c[5001], gmax;
int cmax[5001], uz[10001][5001];

int main()
{
    citire();
    pd();
    afisare();
    return 0;
}

void citire()
{
    int i;
    fin>>n>>gmax;
    for(i=1;i<=n;i++)
        fin>>w[i]>>c[i];
}

void pd ()
{
    int g, i, j, poz, x;
    for(g=1;g<=gmax;g++)
    {
        poz=0;
        for(i=1;i<=n;i++)
        {
            if(w[i]<=g && uz[g-w[i]][i]==0)
                x=c[i]+cmax[g-w[i]];
            else
                x=c[i];
            if(x>cmax[g])
            {
                poz=i;
                cmax[g]=x;
            }
        }
        if(poz)
        {
            for(j=1;j<=n;j++)
                uz[g][j]=uz[g-w[poz]][j];
            uz[g][poz]=1;
        }
    }
}

void afisare()
{
    int g, i, mx, poz;
    for(g=1;g<=gmax;g++)
        if(mx<cmax[g])
        {
            mx=cmax[g];
            poz=g;
        }
    fout<<mx<<'\n';
    for(i=1;i<=n;i++)
        if(uz[poz][i]==1)
            fout<<i<<' ';
    fout<<'\n';
}