6

当有超过 1 个财产时，我在理解背包问题时遇到了问题。当有 1 个属性时，

我必须编写一个使用具有 2 个属性的背包算法的程序。老师告诉我们，它必须在一个 3d 数组中完成。错误的实现将导致 O(2^n) 处理时间。我无法想象这样的阵列会是什么样子。

假设这是我的输入：

4 3 4 // number of records below, 1st property of backpack, 2nd property  of backpack
1 1 1 // 1st property, 2nd property, cost
1 2 2 // 1st property, 2nd property, cost
2 3 3 // 1st property, 2nd property, cost
3 4 5 // 1st property, 2nd property, cost

输出看起来像这样：

4    // the cheapest sum of costs of 2 records
1 3  // numbers of these 2 records

输出说明： 2 组记录适合第一行输入：

(1) - 记录号 1 和记录号 3

  1 1 1
+ 2 3 3
-------
  3 4 4

(2) - 记录号 4

  3 4 5

因为第一组记录是最便宜的（4 < 5），所以我们选择了它。我不仅要查明是否存在这样的记录集，还要找到我总结的记录。

但现在，我只需要了解 3d 数组会是什么样子。你们中的一些人能帮我解决这个问题，并像我的形象一样，一层一层地展示，这会是什么样子？谢谢。

4

2 回答 2

3

从用动态规划求解一约束背包问题的算法转换为求解二约束问题是很容易的。对于有人绘制 3d 图像来向您展示那里正在发生的事情，我想这有点困难。另一方面，该算法非常简单：

我假设您想要一个精确匹配的解决方案，并且您想要最小化成本，而不是最大化价值（我从您的示例中得出）。我以前没有做过这些变化，所以我不能保证没有错误。

1-约束

1-约束背包问题的矩阵(item x weight)存储每个位置的值。

该算法基本上是：

// WL = backpack weight limit
A[0, 0] = 0
for w = 1, 2, ..., WL // weight
  A[0, w] = INFINITY
for i = 1, 2, ..., n // items
  for w = 0, 1, ..., WL // weight
    // wi and ci are the weight and cost of the item respectively
    // A[i-1, w-wi] + ci = 0 when wi > w
    A[i, w] = min(A[i-1, w], A[i-1, w-wi] + ci)

2-约束

现在将此扩展到包含另一个约束只是：（假设size是另一个约束）

矩阵将是(item x weight x size)。

// WL = backpack weight limit
// SL = backpack size limit
for w = 0, 1, ..., WL // weight
  for s = 0, 1, ..., SL // size
    A[0, w, s] = INFINITY
A[0, 0, 0] = 0
for i = 1, 2, ..., n // items
  for w = 0, 1, ..., WL // weight
    for s = 0, 1, ..., SL // size
      // wi, si and ci are the weight, size and cost of the item respectively
      // A[i-1, w-wi, s-si] + ci = 0 when wi > w or si > s
      A[i, w, s] = min(A[i-1, w, s], A[i-1, w-wi, s-si] + ci)
于 2013-01-06T02:14:57.317 回答
-2

你正在尝试做一些不可能的事情——那是你的问题。

当您增加维度数量时，您的项目将获得额外的属性。prop1因此，您可以使用矩形边 ( prop1x prop2) 或块边(prop1x prop2xprop3等等，而不是表格的左侧列边 ( )。但是现有的约束，定义表的上排侧，应该具有相同的维度数。不止一维！. 因此，您永远无法将二属性问题放入 3 维块中，而需要 4D 块。3 个属性的 6D 块等等。

于 2012-11-27T09:14:49.653 回答