p1lgr1m

[IMG]http://i218.photobucket.com/albums/cc62/p1lgr1m/adasd.jpg[/IMG]

wmutex

Notand numarul de corturi dintr-un camp cu variabilele din poza de mai jos

Variabile

rezulta urmatoarele ecuatii, date de conditiile problemei.

Nr de corturi pe linie orizontala:

x[1,1] + x[1,2] + x[1,3] + x[1,5] + x[1,6] + x[1,8] + x[1,9] = 3
x[2,1] + x[2,4] + x[2,6] + x[2,7] + x[2,8] + x[2,9] + x[2,10] = 1
x[3,1] + x[3,2] + x[3,3] + x[3,4] + x[3,5] + x[3,6] + x[3,7] + x[3,9] + x[3,10] = 4
x[4,2] + x[4,3] + x[4,4] + x[4,6] + x[4,7] + x[4,8] + x[4,10] = 1
x[5,1] + x[5,3] + x[5,4] + x[5,5] + x[5,6] + x[5,7] + x[5,8] + x[5,9] + x[5,10] = 3
x[6,1] + x[6,2] + x[6,3] + x[6,5] + x[6,6] + x[6,8] + x[6,10] = 2

Nr de corturi pe linie verticala verticala:
x[1,1] + x[2,1] + x[3,1] + x[5,1] + x[6,1] = 2
x[1,2] + x[3,2] + x[4,2] + x[6,2] = 1
x[1,3] + x[3,3] + x[4,3] + x[5,3] + x[6,3] = 2
x[2,4] + x[3,4] + x[4,4] + x[5,4] = 0
x[1,5] + x[3,5] + x[5,5] + x[6,5] = 3
x[1,6] + x[2,6] + x[3,6] + x[4,6] + x[5,6] + x[6,6] = 0
x[2,7] + x[3,7] + x[4,7] + x[5,7] = 2
x[1,8] + x[2,8] + x[4,8] + x[5,8] + x[6,8] = 1
x[1,9] + x[2,9] + x[3,9] + x[5,9] = 0
x[2,10] + x[3,10] + x[4,10] + x[5,10] + x[6,10] = 3

Conditia de cort langa copac:
x[1,1] = 0, x[6,1] = 0
x[4,3] = 0
x[3,4] = 0, x[3,6] = 0
x[5,6] = 0
x[4,7] = 0
x[5,8] = 0
x[2,9] = 0
x[3,10] = 0, x[5,10]=0

Conditiile de corturi neadiacente pe verticala sau orizontala:
x[i,j] + x[i,j+1] < 2,
x[i,j] + x[i+1,j] < 2.

Sistemul de ecuatii de mai sus e nedeterminat, si se rezolva relativ usor pentru x[i,j] ∈ {0,1} (pentru ca putem avea maxim un cort intr-un camp). Reprezentate grafic (gri=camp gol, rosu=camp ocupat de un cort), solutiile posibile ar fi cam astea:


Solutia 1


Solutia 2

Se observa ca solutia 2 nu verifica conditia de ne-adiacenta a corturilor pe diagonala. Nu ramane decat solutia 1 ca solutie valida.

bogdan198731

Alta solutie Imagine ataşată