Pagina per il calcolo dei fabbisogni

[Felotti]

Buongiorno a tutti.
Sto creando, tramite php, una sorta di "programma conta verghe (tubi)".
Mi spiego meglio.
In molte carpenterie sono presenti delle macchine laser che tagliano le verghe (ossia i tubi) in vari pezzi disegnati dagli uffici tecnici.
Queste verghe hanno una lunghezza fissa di 5800 mm.
Ora, mettiamo il caso che in ordine ci sono:
5 pezzi di lunghezza 3000 mm
5 pezzi di lunghezza 2000 mm
5 pezzi di lunghezza 500 mm
e 5 pezzi di lunghezza 300 mm
Per ottimizzare la quantità di verghe da utilizzare, bisogna far si che in ogni verga ci sia il maggior numero di pezzi possibili.
Per esempio:
Verga 1: 1 pezzo da 3000 mm, 1 pezzo da 2000 mm, 1 pezzo da 500 mm e un pezzo da 300mm.
Si procede così fino a quanto le quantità da produrre vengono termitate.
Al giorno d'oggi questa gestione avviene manualmente, ma con l'avvento delle nuove tecnologie bisogna ottimizzarsi sotto ogni punto di vista.
Ora, io mi sto cimentando in questa programmazione ma mi sorgono delle difficoltà (non utilizzando php e html da diverso tempo).
Avevo in mente di chiedere all'utente il numero di articoli da dover tagliare (nell'esempio precedente 4 per intenderci), in modo da generare un array multidimensionale composto da 4 righe.
Tramite il metodo POST (o anche GET dato che non sono dati sensibili), ricevere questa informazione dalla pagina html e generare questo array dove si richiedono anche:
Dimensioni dei pezzi, quantità e codice articolo.
Avendo un risultato del genere:
$fabbisogni = array(
"Codice" => array ();
"Dimensione" => array ();
"Quantità" => array ();
);
Dopodichè, tramite cicli for e while, ottimizzare l'utilizzo delle verghe e stampare a video il numero di verghe utilizzate ed il modo in cui vengono utilizzate, per ottenere un risultato simile:

Numero verghe utilizzate: 5
Verga 1: codice1 (3000 mm quantità 1), codice2 (2000mm quantità 1) ...... e così via.
Verga 2: .....
.....

N.B: Se in una verga avanzano, per esempio, 200 mm, ma il pezzo più piccolo misura 300 mm, non posso utilizzare questi 200 mm e 100 mm di un'altra verga. La quantità rimasta sarebbe dunque da considerare "scarto".

Mi sorgono delle difficoltà nella creazione dinamica di questi array e nei cicli.
In particolare nei seguenti punti:

• Permettere all'utente di aggiungere articoli in base alle necessità (non sapendo a priori di quanti articoli differenti necessita).Sostanzialmente dovrei inserire un pulsante "+" chie aggiungerà due tre campi di testo ("codice articolo", "lunghezza" e "quantità").
• Memorizzare i dati in un array composto da altri 3 array ("codice articolo", "lunghezza", "quantità")
• Creazione di un ciclo che scorra gli aray "lunghezza" e "quantità". Questo ciclo, partendo dalla misura del tubo "nuovo" (lunghezza fissa memorizzata in una variabile "tubo"), comincerà a sottrarre i tubi da tagliare, verificando sempre se il più lungo ci possa stare o altrimenti passando immediatamente a quello più corto e così via
• Ogni volta che un tubo viene terminato memorizzare gli articoli tagliati all'interno di quel tubo in un ulteriore array che verrà stampato a video al termine di tutti gli articoli richiesti dall'utente
• Ogni volta che un tubo arriva a "0" o comunque non c'è pià spazio per tagliare altri pezzi, "tubo" ritorna alla sua lunghezza fissa di partenza e la variabile "tubi utilizzati" aumenta di 1.
  
  Come risultato finale l'utente avrà:
• Numero di tubi utilizzati
• Come viene tagliato ogni singolo tubo
  
  So che chiedo tanto, tantissimo, ma non riesco veramente a tirarmene fuori

Qualcuno può darmi una mano?

Grazie in anticipo

[Alhazred]

Non è un problema banale da risolvere, bisogna elaborare un algoritmo che valuti le varie combinazioni di tagli relative all'ordine ricevuto, che alla fine di ogni tentativo si ricordi la combinazione migliore e la restituisca alla fine.
Un metodo becero sarebbe quello di provare tutte le combinazioni in sequenza su tutti i pezzi richiesti, per esempio ti si chiedono
2 pezzi da 2600
2 pezzi da 1800
1 pezzo da 900

combinazione 1:
2600 + 2600 -> 5200 -> 1 verga, scarto 600
1800 + 1800 + 900 -> 4500 -> 1 verga, scarto 1300
scarto totale 1900 -> miglior risultato corrente

combinazione 2:
2600 + 1800 + 900 -> 5300 -> 1 verga, scarto 500
2600 + 1800 -> 4400 -> 1 verga, scarto 1400
scarto totale 1900 -> come il precedente

in pratica un sacco di cicli, che puoi ottimizzare fermandoli quando si sfora la lunghezza di una verga e tenendo sempre aggiornato lo scarto totale della combinazione corrente in modo da confrontarlo con il migliore ottenuto in precedenza e passare subito alla combinazione successiva se diventa maggiore o uguale, sarebbe inutile insistere su una combinazione se già in un punto intermedio risulta uno scarto maggiore.

Insomma, c'è da perderci del tempo per scrivere un buon algoritmo che faccia ciò che ti serve.

[Felotti]

Ciao Alhazred,
innanzitutto grazie per la risposta.

Ad ogni modo, per quanto riguarda i cicli sto arrivando ad una soluzione anche con l'aiuto di un collega.
Mi servirebbe più che altro una mano per la pagina lato client, ossia per il seguente punto:

- Permettere all'utente di aggiungere articoli in base alle necessità (non sapendo a priori di quanti articoli differenti necessita).Sostanzialmente dovrei inserire un pulsante "+" chie aggiungerà due tre campi di testo ("codice articolo", "lunghezza" e "quantità").

Riesci ad aiutarmi?

Grazie in anticipo

[Alhazred]

...
- Permettere all'utente di aggiungere articoli in base alle necessità (non sapendo a priori di quanti articoli differenti necessita).Sostanzialmente dovrei inserire un pulsante "+" chie aggiungerà due tre campi di testo ("codice articolo", "lunghezza" e "quantità").

Riesci ad aiutarmi?

Grazie in anticipo

Questo dovrai farlo con Javascript, PHP non agisce lato client, per motivi di organizzazione del forum dovresti chiedere aiuto per questo nella sezione Javascript.

[Felotti]

Si hai ragione scusami, chiedevo info di HTML nella sezione errata, pardon
Ad ogni modo, ho fatto una bozza del codice in una maniera alternativa rispetto a come avevo fatto in precedenza.
Come ti pare?

<?php

$lunghezze_pezzi = array ("3000", "2000", "500", "800"); //array lunghezze pezzi
$quantita = array ("5", "5", "5", "5"); //array quantità
$tubo_corrente = array (); //memorizzo in che modo vengono tagliato il tubo
$risultato = array(); //array composto dai vari array dei tubi tagliati
$sfridi = array (); //verifico gli sfridi di verga in verga
$tubo = 5800; //lunghezza iniziale tubo
$verghe_tagl = 0; //numero di verghe utilizzate

for($i=0; $i<count($lunghezze_pezzi); $i++){ //scorrimento array lunghezze
for($j=0; $j<count($quantita); $j++){ //scorrimento array quantità
if($i!=0){ $n=$lunghezze_pezzi[$i-1]; //variabile per verifica valore maggiore
}else $n=0; //se sono al primo ciclo la variabile per la verifica del valore maggiore rimane a 0
if($lunghezze_pezzi[$i] > $n && $quantita[$j] != 0){ //verifico che il pezzo abbia una lunghezza maggiore del precedente e che la sua quantità non sia 0
$n=$lunghezze_pezzi[$i]; //aggiungo la dimensione più lunga dei tubi da tagliare alla variabile di inserimento
}
if($tubo > $n){ //controllo che il tubo abbia la dimensione necessaria al taglio di quel pezzo
$tubo=$tubo-$n; //taglio il tubo togliendo la quantità tagliata
$quantita[$j]=$quantita[$j]-1; //diminuisco di 1 la quantità del tubo tagliato
array_push($tubo_corrente, $n); //inserisco nell'array dei pezzi tagliati in ogni verga la dimensione del pezzo appena tagliato
}else{
for($k=0; $k<count($lunghezze_pezzi); $k++){ //verifico se ci sono altri pezzi da poter tagliare nel tubo
if($tubo > $lunghezze_pezzi[$k] && $quantita[$k] != 0) $temp=1; //se ce ne sono metto la variabile di controllo a 1
else{
$temp=0; //se non ce ne sono la variabile andrà a 0
$verghe_tagl += 1; //dato che il tubo è stato completamente tagliato, aumento la quantità delle verghe utilizzate di 1
array_push($sfridi, $tubo); //memorizzo lo sfrido della verga appena tagliata
$tubo = 5800; //riporto la variabile tubo alla lunghezza max dato che cambierò tubo
}
}
if($temp=0){ //verifico che non ci siano più pezzi che ci possano stare nello sfrido
array_push($risultato, $tubo_corrente); //inserisco l'array dei pezzi tagliati nel tubo all'interno dell'array che conterrà tutti i tubi tagliati
$tubo_corrente=array(); //riporto l'array del tubo corrente a 0 in modo che si possa iniziare un altro tubo da capo
}
}
}
}
for($z=0; $z<count($lunghezze_pezzi); $z++){ //controllo se ci sono ancora dei pezzi da tagliare
if($quantita[$z] !=0) $x=1; //se ne restano altri metto la variabile x a 1
}
if($x=0){
echo $risultato; //stampo come vengono tagliati i tubi
echo $verghe_tagl; //stampo il numero di verghe utilizzate
}
?>

[Felotti]

Ovviamente avrò sbagliato un sacco di cose di sintassi e di logica, però come ripeto non metto le mani su PHP da qualche anno

[Alhazred]

Il tuo codice mi termina subito senza stampare nulla.

Comunque bisogna trovare un algoritmo intelligente, perché già solo generare tutte le permutazioni derivanti dall'ordine dell'utente diventa subito un calcolo mostruoso, il numero di permutazioni semplici è n! con n pari al numero di pezzi richiesti.

Con 9 pezzi ci mette molto a generare tutte le permutazioni (362.880), ma le gestisce.
Con 10 pezzi (3.628.800 permutazioni) la memoria va in overflow, avendo PHP in uso 128MB sul mio server e quella è in genere la quantità che hai a disposizione.

[Vincent.Zeno]

ricorda anche di sottrarre la misura del taglio dal totale disponibile per singola verga:
una verga da 5800 mm, tagliata in 4 parti, non crea 4 pezzi da 1450 mm... ma un po' meno.

[Felotti]

Grazie ad entrambi per i suggerimenti.
Alla fine ho rifatto completamente il codice e sono riuscito a creare il programma

[Vincent.Zeno]

potresti esporci la logica che hai applicato? può tornare utile...