Pseudocódigo para apilar estantes

Question

Supongamos que tengo algunos elementos numerados en serie que tienen 1-n unidades de ancho, que deben mostrarse en filas. Cada fila tiene m unidades de ancho. Necesito un pseudocódigo que generará las filas, para mí, de modo que se mantenga el límite de ancho m. Esto no es un problema de mochila, ya que los elementos deben permanecer en orden de número de serie: los espacios vacíos al final de las filas están bien.

He estado persiguiendo mi cola sobre esto, en parte porque lo necesito tanto en PHP como en jQuery / javascript, de ahí la solicitud de pseudocódigo ...

Answer 1

while (!items.isEmpty()) {
  rowRemain = m;
  rowContents = [];
  while (!items.isEmpty() && rowRemain > items[0].width) {
    i = items.shift();
    rowRemain -= i.width
    rowContents.push(i);
  }
  rows.push(rowContents);
}

El tiempo de ejecución es & # 920; (número de elementos)

Answer 2

Modulus es tu amigo. Haría algo como:

$items = array(/* Your list of stuff */);
$count = 0;
$maxUnitsPerRow = 4; // Your "m" above

while ($item = $items[$count]) {
 if ($count % $maxUnitsPerRow == 0) {
    $row = new row();
 }
$row->addItemToRow($item);
$count++;
}

Answer 3

Aquí hay un código php alternativo ...

function arrayMaxWidthString($items, $maxWidth) {
    $out = array();
    if (empty($items)) {
        return $out;
    }

    $row = $maxWidth;
    $i = 0;

    $item = array_shift($items);
    $row -= strlen($item);
    $out[0] = $item;

    foreach ($items as $item) {
        $l = strlen($item);
        $tmp = ($l + 1);
        if ($row >= $tmp) {
            $row -= $tmp;
            $out[$i] = (($row !== $maxWidth) ? $out[$i] . ' ' : '') . $item;
        } elseif ($row === $maxWidth) {
            $out[$i] = $item;
            ++$i;
        } else {
            ++$i;
            $row = $maxWidth - $l;
            $out[$i] = $item;
        }
    }
    return $out;
}

Answer 4

Por lo que vale, creo que tengo lo que estaba buscando, para PHP, pero no estoy seguro de si hay una manera más simple ...

<?php
// working with just a simple array of widths...
$items     = array(1,1,1,2,1,1,2,1);
$row_width = 0;
$max_width = 2;

echo "Begin\n"; // begin first row
foreach($items as $item=>$item_width) {
  // can we add item_width to row without going over?
  $row_width += $item_width;
  if($row_width < $max_width) {
    echo "$item_width ";
  } else if($row_width == $max_width) {
    echo "$item_width";
    echo "\nEnd\nBegin\n"; // end last row, begin new row
    $row_width = 0;
  } else if($row_width == 2* $max_width) {
    echo "\nEnd\nBegin\n"; // end last row, begin new row
    echo "$item_width";
    echo "\nEnd\n"; // end new row
    $row_width = 0;
    if($item < count($items)) echo "Begin\n"; // new row
  } else if($row_width > $max_width) {
    echo "\nEnd\nBegin\n"; // end last row, begin new row
    echo "$item_width";
    $row_width = $item_width;
  }
}
echo "\nEnd\n"; // end last row

?>