Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 03-05-2012 08:53:53

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 802
Lieu: Seahaven island

brainstorming variante probleme sac à fos.

Hello,

Je m'intéresse au probleme suivant:
-On fournit une liste finie d'entiers (positif ou négatif)
-Ainsi qu'une somme S, un entier également.
-Le but étant de déterminer si on peut ou non obtenir S par sommation d'une partie des entiers données.

Remarque sur le probleme:
C'est une de nombreuse variante du probleme du sac à dos. Cette variante est NP-complete etc...  (donc bon bref on ne trouvera rien de trivial pour répondre a la question).

Personnellement je m'intéresse à tous les criteres rapidement calculables (en temps polynomial) permettant de déduire qu'on ne peut pas obtenir S.

Par exemple:
-Si S est strictement plus grand que la somme de tous les entiers positifs de la liste il est claire qu'on aura aucune chance d'obtenir S. (de la même manière strictement inférieur, entier négatif etc...)
-Après il y a des criteres de divisibilité du genre si S est impair et que tous les éléments de la listes sont pairs, idem on peut conclure que c'est impossible.
Ce dernier critère peut légèrement s'élargir: On choisit un entier k, on calcule le modulo k de chaque entier de la liste et de la somme, si le modulo de la somme est strictement plus grand que la somme des modulo des éléments de la liste on ne pourra pas obtenir S.

Et vous à quels critères pensez vous? Citez n'importe quel cas particuliers vous permettant de rapidement conclure qu'on ne peut pas obtenir S.



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 03-05-2012 18:17:05

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3311

brainstorming variante probleme sac à doq.

Si S est un nombre premier somme d'un nombre pair d'éléments et que les éléments sont une suites de nombres premiers amicaux.

Si S est premier, on élimine les nombres pairs, les sommes de 2N éléments impairs  et certainement d'autres critères mais c'est tout ce que j'ai en tête.

Shadock


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #3 - 03-05-2012 18:56:13

Klimrod
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 3759
Lieu: hébesphénorotonde triangulaire

Brainstorming varante probleme sac à dos.

Si S est plus petit que le plus petit des éléments de la liste ! cool

Ah zut ! je n'avais pas vu qu'on était dans les entiers relatifs...
Bon je m'en vais...
Klim.


J'ai tant besoin de temps pour buller qu'il n'en reste plus assez pour bosser. Qui vit sans folie n'est pas si sage qu'il croit.

 #4 - 04-05-2012 18:19:06

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

Brainstorming vriante probleme sac à dos.

Si n nombres dans la liste, le maximum de sommes différentes que tu peux faire est 2^n -1. C'est un max compte tenu des possibles redondances.

Sinon, pour trouver un S donné, c'est un peu la même démarche que pour trouver si un nombre est premier. Je ne vois pas trop de possibilités de raccourcis. Beau problème en tout cas.

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez (numériquement) à la petite énigme suivante : 

Un berger a 40 moutons, ils meurent tous sauf 18, combien en reste-t-il ?

Sujets similaires

Sujet Date Forum
P2T
Probleme de groupes par herve22
06-12-2007 Blabla
P2T
Oulipo. par MthS-MlndN
20-05-2008 Blabla
P2T
24-06-2011 Blabla
P2T
Votre profil astral par MthS-MlndN
06-03-2009 Blabla
P2T
06-05-2011 Blabla
05-04-2008 Blabla
P2T
70 ans. par ravachol
08-10-2010 Blabla
P2T
Initiales secretes ? par legeneral
29-10-2008 Blabla
P2T
Merci par gaara2a
07-11-2016 Blabla

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete