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
3 2 1 | 0 |
5
1 2 3 4 7 | 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: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB