装箱问题动态规划提问

Question

您有n1个大小为s1的物品，n2个大小为s2的物品和n3个大小为s3的物品。您希望将所有这些物品装入容量为C的箱子中，使使用的总箱数最小。

我们如何实现使用最少数量的箱子来解决此问题？贪心算法并不一定有效。

- Akash Agrawal

---

作业是哪门课的？ - H H

@Henk：反正这不是作业，我已经离开大学6年了。这可能是一个愚蠢的问题，但我自己无法解决子问题。 - Akash Agrawal

这也不是一个适合在SO上提问的具体问题。可以去理论计算机科学(见页脚)讨论，或者先尝试一些内容再来这里询问关于分号的问题。 - H H

各位请注意，这个问题与 SO 的主题相关。有一个问题需要回答... - Aryabhatta

贪心算法（或任何P问题的解决方案）永远不会“肯定有效”（保证最优解）用于装箱问题（或任何NP问题），也不是其旨在解决的。 - Rein Henrichs

Answer 1

我认为这不是一个愚蠢的问题。

一般来说，装箱问题被认为是NP完全问题。

但是，在您的情况下，固定数量物体重量的装箱问题是一个有趣的变种。

下面的论文声称有一个多项式时间算法，可以接近最优解： http://linkinghub.elsevier.com/retrieve/pii/S0377221706004310 当您允许3种不同大小时。(注意：我只看了摘要部分。)

因此，我猜测这个版本也是NP难的，贪心算法可能不起作用。动态规划也不太确定（装箱问题是强NP完全问题）。

希望有所帮助。

- Aryabhatta

Answer 2

这可能不是很高效，但你可以通过一个简单的动态规划（DP）算法来解决这个问题。如果你有固定数量的尺寸，那么它将是输入的多项式，其次数取决于你所拥有的不同尺寸的数量。

我提供了一个实现，对于3种不同的尺寸，它将是O(n1 * n2 * n3 * (C/s2) * (C/s3) * ((n1s1 + n2s2 + n3s3)/C))，而且常数还相当糟糕。（这个数字来自于可用性不同模式的数量为O(n1 * n2 * n3)，对于每一个模式，我们生成O((C/s2) * (C/s3))个可能的下一个箱子进行尝试，对于其中的每一个，我们必须使用一个大小为O((n1s1 + n2s2 + n3s3)/C))的箱子集合。一些常规的优化可以大大加快此程序的速度。）

#!/usr/bin/env python3 -B -u
#-*- coding: utf-8 -*-

import sys
import heapq

def min_bins(bin_size, sizes, counts):
    available = zip(sizes, counts)
    available.sort(reverse=True)
    seen = set([])
    upcoming = [(0, available, [])]
    while 0 < len(upcoming):
        (n, available, bins) = heapq.heappop(upcoming)
        for (bin, left) in bin_packing_and_left(bin_size, available):
            new_bins = bins+[bin]
            if 0 == len(left): return new_bins
            elif left not in seen:
                heapq.heappush(upcoming, (n+1, left, new_bins))
                seen.add(left)

def bin_packing_and_left(bin_size, available, top=True):
    if 0 == len(available): yield ((), ())
    else:
        (size, count) = available[0]
        available = available[1:]
        for (bin, left, used) in bin_packing_and_left_size(bin_size, available):
            can_use = (bin_size-used)/size
            if count <= can_use:
                yield(((size, count), )+bin, left)
            elif 0 < can_use:
                yield(((size, can_use), )+bin, ((size, count-can_use), )+left)
            else: yield(bin, ((size, count), )+left)

def bin_packing_and_left_size(bin_size, available):
    if 0 == len(available): yield ((), (), 0)
    else:
        (size, count) = available[0]
        available = available[1:]
        for (bin, left, used) in bin_packing_and_left_size(bin_size, available):
            for i in range(1+min(count, (bin_size-used)/size)):
                if count == i:
                    yield(((size, count), )+bin, left, used+size*count)
                elif 0 < i:
                    yield(((size, i), )+bin, ((size, count-i), )+left, used+size*i)
                else: yield(bin, ((size, count), )+left, used)

if __name__ == "__main__":
    answer = min_bins(23, (2, 3, 5), (20, 30, 40))
    print(len(answer), answer)

- btilly

---

O(C)或O(s1)并非多项式时间。输入的大小为log（n1 * n2 * n3 * s1 * s2 * s3 * C）。你似乎已经证明它不是强NP-难问题，但还是值得赞赏的 :-) - Aryabhatta

@Moron：啊，你说得对。我总是忘记我们以输入的位数而不是数字的大小来考虑输入的大小。 - btilly

我在输入min_bins(6000, (200, 10, 500, 100, 50, 1000), (2, 80, 10, 100, 150, 2))上运行了这个实现（实际上这是我出于实际原因所需的数量级），大约10分钟后我放弃了，因为该过程消耗了超过2.5 GB的内存 :) - Adrian Petrescu

@AdrianPetrescu 我并不感到惊讶。你有4800万个可能出现的箱子组合，这些组合被存储为复杂的数据结构。原则仍然可以工作，但你必须密切关注内存。更糟糕的是，即使计数增加了一点点，你需要的内存也会增加很多。 - btilly

@evandrix 在删除错误声明之前，请确保它们确实是不正确的。它们可能只需要澄清。在这种情况下，我们被要求提供固定数量的尺寸，对于这种情况，它是多项式的。 - btilly

Answer 3

这可以在 O(n1*n2*n3) 的时间复杂度内完成...

假设 f(i,j,k) 是需要放置大小为 s1、s2、s3 的 i、j 和 k 个物品所需的最小箱数。

注意: C 是箱子的容量

f(i,j,k) 包含两种信息：

a) (当前所需的最小箱数) - 1。称之为属性 B1。

b) 最后一个可用于进一步填充的箱子的当前大小。称之为属性 B2，其中 0 < B2 <= C

因此，递归公式如下：

f(i,j,k)([B1],[B2]) =
  min 
 { 
    f(i-1, j, k)( [B1] + [B2 + S1]/(C+1) , [B2 + S1] <=C ? [B2 + S1] : [B2 + S1 - C]) ,
    f(i, j-1, k)( [B1] + [B2 + S2]/(C+1) , [B2 + S2] <=C ? [B2 + S2] : [B2 + S2 - C]) ,
    f(i, j, k-1)( [B1] + [B2 + S3]/(C+1) , [B2 + S3] <=C ? [B2 + S3] : [B2 + S3 - C])
 }

所需最少箱数为：1 + f(n1, n2, n3)[B1]。其中n1、n2、n3为相关数据，f为函数，B1表示需要的箱子类型。

- cyanide_basu

Answer 4

这是一个关于DP算法的草图。

递归关系：我们对 B(i, j, k) 进行递归，它表示容量为C的最小箱数，用于装载大小为s1的i个物品，大小为s2的j个物品和大小为s3的k个物品。递归关系如下：

B(i, j, k) = min {B (x,y,z) , B(i-x, j-y, k-z)} 
where 0<=x<=i; 
0<=y<=j; 
0<=z<=k

至少有一个变量 x、y 或 z 必须大于 0，且其中一个变量 x、y 或 z 必须小于分别为 i、j 或 k。

运行时间：B 的大小为 O(n3)，计算 B 的每个元素需要 O(n3) 的时间，总时间为 O(n6)。

- Deepti Jain

Answer 5

如果我们能找到一个箱子的最优解，也就是说我可以在一个箱子中放置的元素数量最大，那么这将导致答案。

假设我可以在一个箱子中放置大小为S1的a个元素，大小为S2的b个元素，大小为S3的c个元素。因此，我可以在一个箱子中放置的最大尺寸为K = a * S1 + b * S2 + c * S3。所以答案将是（n1 * S1 + n2 * s2 + n3 * s3）/ K +（n1 * S1 + n2 * s2 + n3 * s3）％K个箱子。

找到K比标准背包问题更容易。如果我假设所有i的最优值存在于1≤i≤C，则可以递归地写出i + 1的最优值。

M(i+1) = max(M(i),M(i-S1)+S1,M(i-S2)+S2,M(i-S3)+S3).

- Raman Gupta

Answer 6

如果可以将问题简化为一维装箱问题，则应使用此处使用的贪心算法：http://www.developerfusion.com/article/5540/bin-packing。

- Micromega

Answer 7

如果尺寸是一维的，或者可以被简化为一维值，那么你可以将其解决为多重背包问题（MKP），其中物品的重量等于其价值。如果你将#bin设置为可用物品数量的上限（一眼看去，如果你的实例不是非常高，这个值可以是#items），你可以使用分支定界或其他优化算法来最优地解决这个问题。如果你可以接受一个非最优解，那么有一些可行的贪心算法。

然而，我并不确定，因为我从未深入研究过这个问题。不过，有一本名为“背包问题”的书介绍了公式和算法，包括装箱问题。在互联网上很容易找到它的PDF版本。

希望这能帮到你。祝你好运。

- PEdroArthur

Answer 8

假设装箱完美，最小箱数为B = ceiling( sum(n(i)*s(i) for i in 1..3) / C )

使用所谓的first_fit（实际上是worst_fit），并进行交换，从这里开始，看看物品是否适合B个箱子。如果不适合，则增加B并重复，直到它们适合。

- Paddy3118

Answer 9

这个函数是最优子函数之一

1. 首次适应算法
2. 最佳适应算法
3. 最坏适应算法

等等。

function ElementFit(weight, c) {
  let sum = 0,
    p = 1,
    temp = 0,
    index = 0;
  let str = "";
  let bin_index = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
  let bin_sum = [0, 0, 0, 0, 0, 0, 0];
  // Place items one by one
  for (let i = 0; i < weight.length; i++) {
    bin_sum = [0, 0, 0, 0, 0, 0, 0];
    for (let k = 0; k < p; k++)
      for (let j = 0; j <= i; j++) {
        if (bin_index[j] == k + 1) bin_sum[k] += weight[j];
      }
    for (let a = 0; a < p; a++) {
      if (bin_sum[a] + weight[i] <= c) {
        bin_index[i] = a + 1;
        break;
      } else if (a == p - 1) {
        p += 1;
        bin_index[i] = p;
        break;
      }
    }
    if (p > 1) {
      temp = weight[i];
      index = i;
      for (let k = 1; k < p; k++)
        for (let j = 0; j < i; j++)
          if (bin_index[j] == k)
            if (temp > weight[j])
              if (bin_sum[k - 1] - weight[j] + temp <= c) {
                bin_index[index] = k;
                bin_index[j] = p;
                bin_sum[k - 1] = bin_sum[k - 1] - weight[j] + temp;
                temp = weight[j];
                index = j;
              }
    }
  }
  for (let k = 0; k < p; k++)
    for (let j = 0; j < weight.length; j++) {
      if (bin_index[j] == k + 1) bin_sum[k] += weight[j];
    }
  for (let k = 1; k <= p; k++) {
    let number = bin_sum.indexOf(Math.max(...bin_sum));
    for (let i = 0; i < weight.length; i++)
      if (bin_index[i] == number + 1) {
        str = str + weight[i].toString();
        str += ",";
      }
    bin_sum[number] = 0;
  }
  return str;
}
let weight = [900, 900, 1000, 100, 50, 32, 30, 15];
let c = 1045;
console.log(ElementFit(weight, c));

- Mohammad Mansoori

---

这并没有回答问题，即使它回答了，一堆没有注释的代码和一个晦涩难懂的解释也不会有什么帮助。 - kuroi neko