Witajcie,

mam małą zagwostkę algorytmiczną. Mamy półkę o szerokości X. Na półce stawiamy pudełka, każde z nich może mieć inną szerokość. Zadaniem jest znaleźć wszystkie możliwe rozstawienia tych pudełek na półce w taki sposób, że między pudełkami musi znaleźć się przynajmniej jedno pole przerwy. Pudełka muszą być rozstawione w odpowiedniej kolejności.

Przykład:


Jak najprościej rozwiązać taki problem?

EDIT

Problem można sprowadzić do znalezienia kombinacji pustych pól, który można sformułować następująco:


Czyli dla przykładu powyżej:


To jednak nie wszystkie rozwiązania, kombinuję dalej.

Poradziłem sobie.

Stworzyłem funkcję, która zwraca wszystkie możliwe indeksy poszczególnych pudełek. Kod:

[PHP] pobierz, plaintext 
function getCombinations(array $blocks, $length) {
	$result = array();
	$blocksNumber = count($blocks);
 
	// init result
	$positions = array();
	$position = 0;
	foreach($blocks as $block) {
		$positions[] = $position;
		$position += $block + 1;
	}
	$result[] = $positions;
 
	// move each block to the right
	for($index = $blocksNumber - 1; $index >= 0; $index -= 1) {
		$new = array();
		foreach($result as $positions) {
			while($positions[$index] < ($index < $blocksNumber - 1 ? $positions[$index + 1] - $blocks[$index] - 1 : $length - $blocks[$index])) {
				$positions[$index] += 1;
				$new[] = $positions;
			}
		}
		$result = array_merge($result, $new);
	}
 
	return $result;
}
[PHP] pobierz, plaintext 

Przykład: Mamy 3 pudełka o szerokości kolejno 3, 1 i 2. Półka ma szerokość 10. Wynik:


Graficzna prezentacja wszystkich ustawień na półce:


Dla potomnych