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 : 844
Lieu: Seahaven island

Brainstormin gvariante probleme sac à dos.

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 : 3332

Brainstorming variante problmee sac à dos.

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 : 3823
Lieu: hébesphénorotonde triangulaire

brainstorming variante problzme 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 : 3168

Brainstorming variane 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 : 

Si il y a 78 pommes et que vous en prenez 43, combien en avez-vous ?

Sujets similaires

Sujet Date Forum
P2T
Probleme de groupes par herve22
06-12-2007 Blabla
P2T
Copier coller par gwen27
04-04-2016 Blabla
P2T
05-04-2008 Blabla
P2T
Champaaaagne ! par MthS-MlndN
13-01-2009 Blabla
04-06-2008 Blabla
P2T
Musicals at Oscars par HAMEL
23-02-2009 Blabla
P2T
14-12-2014 Blabla
23-06-2011 Blabla
P2T
Bonne année 2010 par EfCeBa
01-01-2010 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