@Mike888

Il y a forcément des solutions. Au pire, en reprenant le mode de fonctionnement que vous aviez dans les années passées, ça donne des solutions qui sont compatibles avec les nouvelles règles du jeu.
Du coup, tu initialises une solution en appliquant les anciennes règles du jeu, et ensuite tu fais des permutations.

Etape 1 : chaque personne doit offrir exactement la liste de telle autre personne.
Etape 2 : Si il y a 2 objets qui ont tous les 2 le même prix (ou presque le même prix .. ...) , tu permutes ces 2 objets, en respectant les règles de mini/maxi. Et tu répètes cette étape 2 50 ou 60 fois, pour s'éloigner le plus possible du résultat obtenu à la fin de l'étape 1.
Tu dois même pouvoir arriver à un résultat où le montant payé par chacun correspond au montant de sa liste. Mais ce sera le challenge pour l'année prochaine.

Pourquoi ton programme ne trouve pas de solution ? Je ne sais pas. Dans ton programme, tu as une fonction random(). Donc tu fais des essais plus ou moins au hasard, en faisant confiance à la chance... Peut être qu'il faut essayer un recensement plus ou moins exhaustif. Un parcours d'arbre. C'est long, mais tu es sur de recenser toutes les combinaisons. Et si tu t'y prends bien, tu peux assez vite éliminer les combinaisons inutiles.

Si tu veux rester avec ton programme actuel, ou avec peu de changements, il y a une astuce à utiliser pour que ton programme ait plus de chances de trouver une solution.
Tu as des objets qui valent 1€, 2€, etc jusqu'à 28€.

Si tu affectes au hasard à telle personne les objets, en commençant par les petits objets, et que les gros objets arrivent à la fin de ton arbre de décision, au moment de caser l'objet à 28€, tu as toutes les chances qu'il n'y ait plus aucune personne qui a le budget pour dépenser encore 28€ de plus.
Au contraire tu peux dire : j'ai des objets chers , je vais déjà affecter l'objet le plus cher à une personne, puis le 2nd plus cher, etc, puis je m'occuperai des objets 'moyens', et enfin, des petits objets. Avec bien sûr, à chaque étape, cette contrainte : Tel objet, je l'attribue à une personne, en choisissant au hasard parmi les personnes qui ont encore le budget.

En procédant ainsi, tu peux faire confiance à la chance et passer par la fonction random(), tu devrais très vite trouver des solutions.