Les tuiles peuvent tourner.
Exemple: P>
donné deux tuiles 1 * 2 et un 1 * 3 tuile, et le plancher est 3 * 3, nous mettons tous les carreaux dans le sol comme Suit: P>
AAA ..B CCB
3 Réponses :
Il peut y avoir des complexités supplémentaires, mais voici mon idée:
remplissez tout le sol avec des tuiles 1x2. Il devrait être assez simple à faire, il suffit de faire en sorte qu'il s'agisse principalement de carreaux parallèles, de quelque chose comme ceci: (noir et blanc sont tous les deux carreaux)
Avis, je viens de remplir la rangée inférieure avec des tuiles horizontales plutôt que verticalement, il s'agit simplement de remplir la grille. Et la tuile inférieure gauche est vide (vous voudrez peut-être remplacer la mosaïque à droite avec une tuile 1x3).
Si vous n'avez pas beaucoup de tuiles 1x2, remplissez toujours la grille complètement, elles seront retirées à l'étape suivante.
Bien que vous n'ayez pas assez de tuiles 1x2 à placer, remplacez systématiquement 3 carreaux 1x2 parallèles avec 2 tuiles 1x3. Donc:
devient 
Grande réponse et images! Je pense que cela fonctionnera également dans le cas particulier, lorsque le sol est 1 * N, ou il y a une ligne qui ne peut pas être couverte par des tuiles parallèles 2 * 1. Dans ce cas, 3 continues 2 * 1 tuile seront remplacées par 2 3 * 1. Donc, en général, il n'est peut-être pas nécessaire de vérifier si les tuiles 3 2 * 1 sont parallèles ou non.
Et après tout, nous devrions vérifier l'espace restant sur le sol. Dans le cas de 1 * 9 étage et donné 0 1 * 2 et 3 1 * 3 tuiles, après remplacement, il y aura un lieu supplémentaire pour une tuile de 1 * 3
Cela peut probablement être transformé en formule, si quelqu'un se sent à essayer de comprendre cela ...
La réponse de Dukeling est fausse. Considérant un étage de 5 * 5 et 8 1 * 3 tuiles. La seule façon de mettre tous les tuiles dans le sol est la suivante:
AAACD BBBCD EF.CD EFGGG EFHHH
Je ne suis pas sûr que la solution de Dukeling a tort. Si nous ne voulons pas utiliser des tuiles parallèles 2 * 1, ou nous ne nous soucions tout simplement pas des rotations, seule la taille, le résultat sera correct. Dans votre échantillon, nous pouvons mettre en baisse 12 1 * 2 carreaux, puis nous pouvons les remplacer par 8 3 * 1 (si nous ne regardons que la taille). Je n'ai pas de preuve, mais je ne peux pas trouver un contre-exemple.
Si vous ne vous souciez que de la taille, votre solution est la même que sa
Je ne dis pas tout à fait que c'est faux. J'ai dit "Il peut y avoir des complexités supplémentaires" . Vous avez simplement souligné qu'une telle complexité est la case ci-dessus, où nous n'avons pas de tuiles de 1x2 et, vraisemblablement également, certains cas où nous avons très peu de tuiles 1x2.
Ce n'est pas clair quoi de retourner. Avez-vous besoin d'un ensemble de solutions ou seulement du nombre maximum? Une solution simple ne peut utiliser que 1 * 2 tuiles. Évidemment, il peut s'adapter à plus de 1 * 2 carreaux puis 1 * 3 tuiles.
Assomption hypothèse B = 0 A = 0 , m> = 3 , n> = 3
Tous les carreaux de sol sont-ils disponibles pour être couverts? Ou certains carreaux de sol sont-ils hors limites au début?
Cela ressemble à 2D-Emballage pour moi. Ce Nice Article regarde pourrait vous aider.
Oui. Chaque grille de sol peut être couverte (si vous le pouvez).
@ G.bach pas vraiment. C'est un problème spécifique et peut avoir une bonne solution.
@Dukeling Vous devriez poster cela comme une réponse. Cela semble être suffisamment optimal pour moi.
Comment A & B est-il choisi?
Je suis raisonnablement sûr que chaque étage 2x2 ou plus puisse être complètement couvert, étant donné une offre sans restriction de tuiles. La complexité serait si vous souhaitez minimiser ou maximiser le nombre de tuiles utilisées et / ou si le nombre de carreaux de chaque taille est restreint.
@Hotlicks vraiment? Quand il s'agit de 5 * 5 et que tous les tuiles sont 1 * 3?
@Sayakiss - "Compte tenu d'une offre sans restriction de tuile
@Hotlicks Je peux le résoudre avec une offre sans restriction de carreaux ...
Pourquoi répondre n'est pas 4 ici?
@Nakilon Parce que vous n'avez que 3 tuiles (2 1x2 et 1 1x3).
La réponse est 42. Maintenant quelle est la question?
Vous pouvez construire un ZDD pour les contraintes (non-chevauchement, couvrir tous les endroits, ne pas sortir du sol), puis obtenez la tâche satisfaisante maximale. Je ne sais pas dans quelle mesure cette balance, mais j'ai utilisée cette technique pour résoudre des problèmes d'Euler de projet qui ressemblaient un peu à ceci.
@harold qu'est-ce que zdd? S'il vous plaît donnez-moi plus d'informations sur zdd
@Dielogik Il y a une explication courte ici: Crypto.stanford.edu/pbc/notes/zddd et plus d'informations détaillées dans l'art de la programmation informatique 7.1.4 (volume 4a)