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

input.txt output.txt
4
10
4 1
5 4
2 1
6 4
8
1
99
2 1
49
8
230
55 60
23 10
4 1
3 1
2 1
30 13
30 11
19 17
245

Notice: This work is licensed under a BY-NC-SA. Permalink: Alì Babà e i quaranta ladroni

Comments are closed.