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

brainstorming variante ptobleme 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 prolbeme 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 probleme sac à dis.

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

Brainstorming variante problmee 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 à la devinette suivante : 

Le père de toto a trois fils : Pim, Pam et ?

Sujets similaires

Sujet Date Forum
P2T
Probleme de groupes par herve22
06-12-2007 Blabla
14-03-2009 Blabla
05-05-2012 Blabla
P2T
10-10-2015 Blabla
01-10-2016 Blabla
P2T
Simple question par Autleaf
24-02-2011 Blabla
22-06-2008 Blabla
P2T
Repose en paix, Alain par JustineF
15-03-2009 Blabla
08-08-2007 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