programmation dynamique: trouver plus grandes places qui ne se chevauchent

Question

je n'ai vraiment aucune idée de comment faire en utilisant la programmation dynamique: Problème: Je dois trouver les 2 plus grandes places non se chevauchent d'une table Par exemple:

5 6 
R F F R R F 
F F F F F F 
R R F F F F 
F F F F F F 
F F F F F F 

Les chiffres 5 et 6 sont respectivement le nombre de rangées et de colonnes, et "R" signifie réservé et "F" signifie libre. Dans ce cas, la plus grande place est

F F F F 
F F F F 
F F F F 
F F F F 

et le deuxième (non-chevauchement avec la précédente) est

F F 
F F 

Jusqu'à présent, j'ai mis les valeurs dans un tableau 2D, mais ne pas savoir quoi faire après. J'ai essayé de faire référence au sac à dos 0-1 et au LCS, mais je n'ai aucune idée des valeurs que je devrais mettre dans ma table.

Answer 1

Eh bien, votre première tâche lors de la conception d'un algorithme de programmation dynamique devrait être de trouver une solution récursive au problème. Après cela, la conversion en un algorithme de programmation dynamique est presque triviale;).

Quelques conseils qui pourraient/ne pouvait pas aider:

Un cas de base possible est évidente: les deux carrés de 1 cellules sont toujours non-chevauchement. Gardez à l'esprit que le plus grand des deux carrés ne peut pas couvrir la totalité de la table (car vous n'en aurez donc pas le deuxième en taille), donc il ne peut pas s'agir de lignes: taille des colonnes. Vous devriez avoir un "score" pour chaque solution que vous évaluez, pour voir quel est le meilleur. Ce score est évidemment de taille 1 + taille2, avec la condition que size1 soit le maximum possible.

Bonne chance !!

Answer 2

Il s'agit d'une variante de Longest Common Substring Problem et non de LCS (plus longue sous-séquence commune). Imaginez deux chaînes que vous comparez comme étant les côtés d'un rectangle avec leurs caractères comme les carrés. Un "F" dans un carré signifierait une correspondance entre deux caractères dans les chaînes, et donc le plus grand carré est la plus longue sous-chaîne commune.