Cod sursa(job #853207)

Utilizator mateidanutDanut Gabriel Matei mateidanut Data 12 ianuarie 2013 11:10:04
Problema Problema rucsacului Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <fstream>
#include <iostream>
#include <iomanip>
using namespace std;
unsigned int N, i, ok;
int w[5001], p[5001], aux, G, gr;
float v;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int main() {
    f>>N>>G;
    for (i=1; i<=N; i++)
        f>>w[i]>>p[i];
    do {
        ok=1;
        for (i=1; i<N; i++)
            if ((float)p[i]/w[i]<(float)p[i+1]/w[i+1]) {
                aux=p[i];
                p[i]=p[i+1];
                p[i+1]=aux;
                aux=w[i];
                w[i]=w[i+1];
                w[i+1]=aux;
                ok=0;
            }
    } while (!ok);
    i=1;
    while (gr+w[i]<G) {
        gr+=w[i];
        v+=p[i];
        i++;
    }
    v+=((G-gr)*(float)p[i]/w[i]);
    g<<v;
    return 0;
}