Zadanie 1001: Optymalizacja Cięcia (Cutting Stock Problem)

Wstęp

W każdym warsztacie stolarskim czy ślusarskim kluczowe jest oszczędzanie materiału. Wyobraź sobie, że masz na stanie 5 długich rur (np. po 6 metrów), a klient zamawia 20 odcinków o różnych długościach. Jak to pociąć, żeby zmarnować jak najmniej? To klasyczny problem algorytmiczny, z którym zmierzysz się w tym zadaniu.

Cel zadania

Napisanie programu w PHP, który przyjmie listę dostępnych materiałów (długości) oraz listę potrzebnych elementów, a następnie wygeneruje "plan cięcia" uwzględniając grubość tarczy tnącej (rzaz).

Wymagania techniczne

Interfejs (HTML/CSS): Dwa formularze – jeden do dodawania "Magazynu" (dostępne profile), drugi do "Zamówienia" (potrzebne odcinki).
Logika (PHP): Algorytm dopasowujący odcinki do profili (np. podejście zachłanne "First Fit").
Parametr techniczny: Uwzględnienie grubości piły (domyślnie 5mm) przy każdym cięciu.
Prezentacja: Wyświetlenie czytelnego raportu (Graficznie lub tekstowo).

Kroki do wykonania

1. Interfejs Użytkownika (UI)

Potrzebujemy prostego widoku, w którym użytkownik wprowadzi dane. Utwórz plik index.php ze strukturą:

Sekcja "Magazyn": Lista inputów lub textarea do wpisania długości posiadanych profili (np. w mm).
Sekcja "Do wycięcia": Lista długości, które chcemy uzyskać.
Ustawienie "Grubość piły" (domyślne 5mm).

<!-- index.php -->
<form method="POST">
    <h3>1. Co masz w magazynie?</h3>
    <textarea name="warehouse" placeholder="np. 2000, 2000, 1500"></textarea>
    
    <h3>2. Co chcesz wyciąć?</h3>
    <textarea name="orders" placeholder="np. 500, 450, 450, 100"></textarea>
    
    <h3>3. Parametry</h3>
    <label>Rzaz (mm): <input type="number" name="kerf" value="5"></label>
    
    <button type="submit">Oblicz rozkrój</button>
</form>

2. Przetwarzanie Danych

W PHP odbierz dane i zamień je na tablice liczb całkowitych. Pamiętaj o walidacji!

<?php
// Rozdziel stringa po przecinkach i zrzutuj na int
$warehouse = array_map('intval', explode(',', $_POST['warehouse']));
$orders = array_map('intval', explode(',', $_POST['orders']));
$kerf = intval($_POST['kerf']);

// Posortuj zamówienia malejąco - to ważna heurystyka!
// Łatwiej upchnąć najpierw duże kawałki, a potem dziury zapchać małymi.
rsort($orders);
?>

3. Algorytm Optymalizacji (First Fit)

Zaimplementujemy podejście "First Fit Decreasing". Dla każdego zamówionego kawałka szukamy pierwszego profilu z magazynu, w którym się on zmieści.

[!NOTE] Pamiętaj: Jeśli odcinasz kawałek 500mm z rury, zużywasz tak naprawdę 500mm + 5mm (na piłę). Ostatni kawałek z rury nie potrzebuje rzazu, ale dla uproszczenia (bezpieczeństwa) możesz przyjąć, że każde cięcie "zjada" rzaz.

Struktura danych wynikowych może wyglądać tak:

$results = []; // Klucz to ID profilu z magazynu, Wartość to lista odcinków
$waste = [];   // Ile zostało z każdego profilu

foreach ($warehouse as $id => $length) {
    $currentLengths[$id] = $length;
    $results[$id] = [];
}

foreach ($orders as $order) {
    $fitted = false;
    foreach ($currentLengths as $id => $remaining) {
        // Sprawdź czy zmieści się odcinek + rzaz
        $needed = $order + $kerf; 
        
        if ($remaining >= $needed) {
            $currentLengths[$id] -= $needed;
            $results[$id][] = $order;
            $fitted = true;
            break; // Przejdź do kolejnego zamówienia
        }
    }
    
    if (!$fitted) {
        echo "Nie udało się dopasować odcinka: $order mm!<br>";
    }
}

4. Wyświetlanie Wyników

Wygeneruj czytelną tabelę lub listę.

<?php foreach ($results as $id => $cuts): ?>
    <div class="result-box">
        <h4>Profil <?php echo $id + 1; ?> (Długość startowa: <?php echo $warehouse[$id]; ?> mm)</h4>
        <p>Cięcia: <?php echo implode(' mm, ', $cuts); ?> mm</p>
        <p>Odpad: <strong><?php echo $currentLengths[$id]; ?> mm</strong></p>
        
        <!-- Wizualizacja paskowa (CSS width %) -->
        <div class="bar-container">
            <?php foreach($cuts as $cut): ?>
                <div class="bar-segment" style="width: <?php echo ($cut / $warehouse[$id]) * 100; ?>%">
                    <?php echo $cut; ?>
                </div>
            <?php endforeach; ?>
        </div>
    </div>
<?php endforeach; ?>

[!IMPORTANT] Commit 1: Działający prototyp z algorytmem First Fit i wizualizacją.

Zadanie dla chętnych: "Best Fit"

Algorytm "First Fit" bierze pierwszą pasującą rurę. Algorytm "Best Fit" szuka takiej rury, w której po odcięciu zostanie najmniej odpadu. Zodyfikuj pętlę, aby zamiast przerywać (break) po znalezieniu pierwszej pasującej rury, przeszukała wszystkie i wybrała tę, która zostawi najmniejszą resztę. Porównaj wyniki obu metod.

Algorytmika: Optymalizacja Cięcia Profili