12

当有 1 处房产时，我确实了解那里发生了什么。当有超过 1 个财产时，我在理解背包问题时遇到了问题。

在此处输入图像描述

我必须编写一个使用具有 2 个属性的背包算法的程序。老师告诉我们，它必须在一个 3d 数组中完成。我无法想象这样的阵列会是什么样子。

假设这是我的输入：

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

1

假设您正在使用一个三维表：A[x][y][z]=k, x: sum 1st property; y：总和第二个属性；z：总和第三个属性；k：最小成本（最大奖励，我更喜欢使用奖励）

所以你迭代项目。假设当前项目是 (p1, p2, p3, reward) ( reward = - cost )。对于每个(x,y,z,k)，您的更新公式：

A[x+p1][y+p2][z+p3] = max(A[x+p1][y+p2][z+p3], A[x+p1][y+p2][z+p3] + reward)

如果 RHS 上的第一项较大，则在 slot 上A[x+p1][y+p2][z+p3]，背包的配置保持静止；否则，您通过A[x+p1][y+p2][z+p3]加上当前项目来更新背包。

希望这能把事情弄清楚。

于 2013-09-08T21:02:03.383 回答
0

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

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

于 2012-11-27T09:11:44.723 回答