Alì Babà e i quaranta ladroni

Alì Babà è nella grotta dei quaranta ladroni.
Ricchezze inesauribili si palesano davanti ai suoi occhi.
Purtroppo, un piccolo difetto di fabbricazione gli impedisce di usare il tappeto volante per portarle via.
Si deve quindi accontentare del suo zainetto dalle cinghie un po’ lise, che non reggerà più di tanto.

Dovete aiutare Alì Babà a scegliere che cosa portare via dalla grotta.
La grotta contiene diversi tipi di oggetti.
Ogni oggetto ha un peso e un valore.
Chiaramente Alì non può portare via un peso troppo grande o romperà lo zaino.
D’altra parte, ci sono tante scelte possibili su che cosa si può portare via.

Dati in input

Il file input.txt contiene sulla prima riga un intero N che rappresenta il numero dei tipi degli oggetti nella grotta.
Sulla riga seguente c’è un intero P che rappresenta il massimo peso in grammi che lo zaino di Alì può trasportare.
Le seguenti N righe contengono ciascuna due numeri interi separati da uno spazio: il peso in grammi di un tipo di oggetto, e il suo valore in monete d’oro.

Dati in output

Il programma, dopo aver letto il file di input, deve scrivere nel file output.txt una sola riga contenente un intero: il massimo valore in monete d’oro che Alì può portare via dalla grotta in un solo viaggio senza rompere lo zaino.

Assunzioni

1. La grotta è infinitamente fornita: potete portare via un qualunque numero di oggetti di un certo tipo.
2. Lo zaino di Alì è molto pignolo: si rompe anche se trasportate un solo grammo in più di P, ma trasporta senza problemi P grammi.
3. 1 ≤ N ≤ 200
4. 1 ≤ P ≤ 50000
5. 1 ≤ peso di un oggetto ≤ 1000
6. 1 ≤ valore di un oggetto ≤ 1000.

Esempi di input/output

/*
    wwww.valcon.it
    OII 2001 - Fase nazionale - Alì Babà e i quaranta ladroni
*/

#include
#include
using namespace std;

#define NMAX 200
#define PMAX 50000

struct oggetto { int peso, valore; };  // peso e valore di un oggetto
struct oggetto oggetti[NMAX+1];        // peso e valore di tutti gli oggetti
int            valori_pesi[PMAX];      // il valore massimo per ogni peso

int main()
{
	ifstream fin ( "input.txt");
    ofstream fout("output.txt");

    int N;  // n. oggetti
    int P;  // peso massimo dello zaino      
    fin >> N >> P;    
    for(int i=1; i <= N; i++)
        fin >> oggetti[i].peso >> oggetti[i].valore;

    int risposta=0;
    int valore, nvalore,                         // valore, nuovo valore
        npeso;                                   // nuovo peso
    for(int peso=0; peso < P; peso++)            // per ogni peso raggiungibile
    {
        valore=valori_pesi[peso];                   // valore per il peso
        for(int i=1; i <= N; i++)                   // per ogni oggetto
        {    
            npeso=peso+oggetti[i].peso;
            if(npeso <= P)                          // se non supera il peso massimo
            {
                nvalore=valore+oggetti[i].valore;
                if(nvalore > valori_pesi[npeso])    // se supera il valore per nuovo peso
                {
                    valori_pesi[npeso]=nvalore;
                    if(nvalore > risposta)          // se nuovo valore è alto...
                        risposta=nvalore;
                }    
            }
        }
    }

    fout << risposta;
    return 0;
}