Diviser les poids
Étant donnés n poids , il s’agit de les répartir en 2 groupes de façon à minimiser la différence entre la somme des poids de ces deux groupes.
Entrée
La première ligne de l’entrée contient un entier n (1 ≤ n ≤ 20).
La ligne suivante contient n entiers séparés par des espaces (1 ≤ ≤ ).
Sortie
Le programme doit afficher la plus petite différence possible entre les deux groupes.
Exemples
Entrée | Sortie |
|---|---|
3 | 0 |
5 | 1 |
Explication
Premier groupe → 3, second groupe → 1 + 2 = 3
Premier groupe → 1 + 7 = 8, second groupe → 2 + 3 + 4 = 9
Indice
Vous pouvez essayer de diviser les poids de toutes les manières possibles (au total options) et calculer la différence minimale.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB