4

给定n 个容量无限的垃圾箱，我想将m件物品装入其中（每个都有特定的重量），同时尽量减少最重垃圾箱的重量。

这不是一个传统的垃圾箱包装/背包问题，其中垃圾箱的容量有限，并且您试图尽量减少使用的垃圾箱数量；我有一定数量的垃圾箱，并且想全部使用它们以使最重的垃圾箱的重量尽可能低。

这个问题有名字吗？我浏览了许多带有关键词的论文，但我没有发现任何类似的东西。

干杯。

4

2 回答 2

1

如果限制的是 bin 的数量，而不是 bin 的容量，那么这不是 bin 打包，而是多处理器调度问题。

通常，您可以通过 LPT 算法来解决这个问题，结果非常好。不过，需要进行优化，这就是乐趣所在。

于 2012-02-25T18:15:16.450 回答
0

这是二维装箱问题的一种形式。第一个维度是每个 bin 的容量限制（=硬约束），第二个维度是最小化最重 bin 的权重（=软约束）。

使用Drools Planner，我将从云平衡示例开始并像这样实现它：

rule "maxCapacity"
  when
    // When there is a bin ...
    $bin : Bin($binCapacity : binCapacity)
    // ... where the total of the item capacity is bigger than the bin capacity ...
    $itemCapacityTotal : Number(intValue > $binCapacity) from accumulate(
        ItemAssignment(
            bin == $bin,
            $itemCapacity : itemCapacity),
        sum($itemCapacity)
    )
  then
    // ... then lower the hard score with the insufficient capacity
    insertLogical(new IntConstraintOccurrence("maxCapacity",
            ConstraintType.NEGATIVE_HARD,
            $itemCapacityTotal.intValue() - $binCapacity,
            $bin));
end


rule "calculateWeight"
  when
    $bin : Bin()
    $itemWeightTotal : Number() from accumulate(
        ItemAssignment(
            bin == $bin,
            $itemWeight : itemWeight),
        sum($itemWeight)
    )
  then
    insertLogical(new BinToWeight($bin, $itemWeightTotal);
end
rule "minimizeWeight"
  when
    BinToWeight($bin : bin, $itemWeightTotal : itemWeightTotal)
    not BinToWeight (itemWeightTotal > $itemWeightTotal,  bin != $bin)
  then
    insertLogical(new IntConstraintOccurrence("minimizeWeight",
            ConstraintType.NEGATIVE_SOFT,
            $itemWeightTotal,
            $bin));
end
于 2011-01-28T07:59:34.340 回答