Gewichte aufteilen
Gegeben
n Gewichte , sollt ihr diese in 2 Gruppen aufteilen, sodass die Differenz ihrer Gesamtgewichte minimal ist.Eingabe
Die erste Zeile der Eingabe enthält eine einzelne Ganzzahl
n (1 ≤ n ≤ 20).Die nächste Zeile enthält
n durch Leerzeichen getrennte ganze Zahlen (1 ≤ ≤ ).Ausgabe
Das Programm soll die kleinstmögliche Differenz zwischen den beiden Gruppen ausgeben.
Beispiele
Eingabe | Ausgabe |
3
3 2 1 | 0 |
5
1 2 3 4 7 | 1 |
Erklärung
- Erste Gruppe → 3, zweite Gruppe → 1 + 2 = 3
- Erste Gruppe → 1 + 7 = 8, zweite Gruppe → 2 + 3 + 4 = 9
Hinweis
Ihr könnt versuchen, die Gewichte auf alle möglichen Arten aufzuteilen und so die kleinste mögliche Differenz zu finden.
Constraints
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB