Bonjour je voudrai avoir de l'aide pour pouvoir coder juste l'algorithme parce que là j'ai un petit peu de mal (puis ensuite dans un des langage que je choisirai) qui me permet de placer des objets de différente longueur (ex: l'objet 1 fait une case, l'objet 2 fait 2 cases etc ...) dans un tableau  à 2 dimensions (10X10), avec une vérification pour que les objets ne se touche pas et ne soient pas au même endroit.
 
Merci pour votre aide.

google Knap-Sack problem et tu auras ce qu'il faut

heu merci pour l'aide mais j'ai du mal a trouver ce qu'il me faut je ne suis pas doué en anglais dsl

En français, ce type de pb se résout par l'algo du sac à dos (knap-sack en anglais)
 
Edit : t'as pas précisé s'il fallait prendre tous les objets pour les mettre dans le tableau ou seulement certains et le critère à optimiser (j'imagine, limiter la place perdue dans le tableau). En effet, s'il faut prendre tous les objets, ce pb se résout avec l'algo LPT (prendre les objets de la plus grande taille à la plus petite).

merci rufo pour ta réponse, enfaite mon algo et à peu près identique a celui d'un combat naval donc il ne faut pas limiter la place perdue dans le tableau. je vais essayer de résoudre mon problème avec ce que tu viens de me donner, si tu as d'autre proposition je suis preneur.

 
Tu ne décrits pas très bien ton problème. Dans ce genre de chose, chaque détail est très important car il y a un algo ou heuristique à chaque pb bien souvent, mais répond à un pb donné dans des conditions précises. Ex : le fait de devoir prendre tous les objets ou pas fait que l'algo est différent.
 
Donc, d'après ce que tu me dis, t'as un nb d'objets n donné (faut donc tous les positionner?), de taille t [1 case; x cases], x <= largeur de la grille du coup (toujours en ligne les objets, pas de forme de type "tétris"?) à placer dans une matrice de dimension [L;C] (L=C forcément ou pas?) avec 1 case minimum d'espace entre chaque objet.
 
J'ai bon dans la description de ton pb à résoudre?

oui c'est vrai que j'aurais du bien décrire mon problème donc pour mon problème:
 
- il y a 5 objets
- les objets sont de forme rectangulaire (donc pas de forme comme tetris)
- l'objet n°1 fait 1 case, l'objet n°2 fait 2 cases, l'objet n°3 fait 3         cases, l'objet n°4 fait 4 cases, l'objet n°5 fait 5 cases
- tous les objets sont à placer
- placement des objets dans un tableau à 2 dimensions de 10X10
- les objets peuvent êtres vertical ou horizontal (c'est l'utilisateur qui choisi)
- les objets ne peuvent pas se toucher ou se monter dessus donc une case minimum d'espace entre chaque objet
 
voila je pense que c'est tout et encore merci pour ton aide

10s avec google
 
http://fr.wikipedia.org/wiki/Probl [...] %C3%A0_dos

 
Tu fais référence à la variation du sac à dos multidimensionnel pour résoudre son pb, c'est bien ça? Par contre, faudra qu'il modifie un peu l'algo pour intégrer al contrainte de séparation entre objets.

oui. c'est exactement l'algo ad hoc

heu j'ai un peu de mal pour les info que vous m'avez donné je ne vois pas comment ces informations peuvent m'aider dans mon problème, puisque dans mon cas c'est juste le place de bateau dans un tableau à 2 dimensions, peut-être que je n'ai pas très bien compris ce qu'il y a d'écrit ou que je n'ai pas bien vu mais je ne vois pas comment ces info peuvent m'aider

Le sac à dos, c'est ton tableau à 2 dimensions, les objets à mettre dans le sac, ce sont tes objets de 1 à n et leur poids, c'est la taille en case. Pas dur à trouver comme similitude
 
Donc ton pb se résout par l'algo du sac à dos multidimentionnel. t'as plus qu'à trouver la description algorithmique de cet algo voire une implémentation et c'est fini... Y'a tout de même à introduire la notion d'espace min entre 2 objets. Ca peut peut-être changer les choses...

l'espace min c'est juste une surcontrainte