Dividere i pesi
Dati
n pesi , l’obiettivo è di suddividerli in 2 gruppi in modo tale che la differenza tra le loro somme sia la più piccola possibile.Input
La prima riga dell’input contiene un unico intero
n (1 ≤ n ≤ 20).La riga successiva contiene
n interi separati da spazio (1 ≤ ≤ ).Output
Il programma deve stampare la differenza minima possibile tra i due gruppi.
Examples
Input | Output |
3
3 2 1 | 0 |
5
1 2 3 4 7 | 1 |
Spiegazione
- Primo gruppo → 3, secondo gruppo → 1 + 2 = 3
- Primo gruppo → 1 + 7 = 8, secondo gruppo → 2 + 3 + 4 = 9
Suggerimento
È possibile provare a dividere i pesi in ciascuna delle possibili combinazioni e calcolare la differenza minima.
Constraints
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB