货架堆叠伪码

Question

假设我有一些连续编号的项目，它们的宽度为1-n个单位，需要以行的形式显示。每行宽m个单位。我需要一些伪代码来为我输出行，这样就可以保持m宽度的限制。这不是背包问题，因为项目必须保持序列号顺序-行尾的空格就可以了。

我一直在追逐这一点，部分原因是我在PHP和jQuery/javascript中都需要它，因此需要伪代码……

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);
}

运行时间为Θ(项目数)

Answer 2

模数是你的朋友。我会这样做：

$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

无论如何，我想我已经得到了我想要的东西，PHP --但不确定是否有更简单的方法……

<?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

?>