背包算法的附加属性

Question

当只有一个属性时，我能理解其中的内容。但是当有多个属性时，我对背包问题的理解存在问题。

我将为您翻译以下内容：

我需要编写一个使用背包算法的程序，其中有两个属性。老师告诉我们，必须在三维数组中完成。我无法想象这样的数组会是什么样子。

假设这是我的输入：

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) - 第1条记录和第3条记录

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

(2) - 记录编号 4

  3 4 5

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

但现在，我只需要了解三维数组的外观。有人能帮我做到这一点，并且逐层显示，就像我的图片一样，它会是什么样子？

谢谢。

- Paulina

---

我不确定我理解你的第一个数组。数组中的值是什么意思？ - gmlobdell

在背包容量为V = 2，有两个体积为V=1的物品时，最多只能放两个V=1的物品。在背包容量为V = 3，有两个体积为V=1的物品时，最多能放置这两个物品，使得该单元格内的v=2。在背包容量为v=3，有物品1,1和2时，最多能放置2个物品（v=1、v=2），以便得到3。单元格内的值是背包的最大容量。 - Paulina

我认为你的老师正在寻找多限制背包问题。 - Saeed Amiri

@Paulina，我想我明白了。你的网格的列是背包当前剩余容量（或其他属性），行是按增加体积顺序排序的各种剩余选择。比如我们有一个容量为6的背包。首先我们添加体积为3的物品，剩余容量为3。然后我们查看3列，在“2”行中，因为我们已经使用了“3”项，那个单元格应该会显示“2”。我们添加“2”物品，剩下容量1。在1列中，我们添加较小的“1”物品，装满背包。我的理解正确吗？ - gmlobdell

1-你正在寻找多限制背包问题。 2-你的第一个图有问题。 3-背包问题是使用动态规划解决的，而不是算术。 - Khaled.K

Answer 1

假设你正在使用一个三维表： A[x][y][z]=k，其中 x: 表示第一属性的总和；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)

如果右手边的第一个项更大，在插槽A[x+p1][y+p2][z+p3]上，背包的配置保持不变；否则，您将通过A[x+p1][y+p2][z+p3]加上当前物品来更新背包。

希望这能让事情更清晰。

- dragonxlwang

Answer 2

你正在尝试做一些不可能的事情-这就是你的问题。

当你增加维度时，你的项目会获得额外的属性。因此，与表格的左侧列（prop1）相比，你有了矩形的一边（prop1 x prop2）或者块的一边（prop1 x prop2 x prop3）等等。但是，定义表格的上行边界的现有约束应该具有相同数量的维度。不仅仅是一个维度！所以，你永远无法将具有两个属性的问题放入一个三维块中，你需要一个四维块。对于三个属性，你需要一个六维块，依此类推。

- Gangnus

---

你能解释一下什么是“附加属性”吗？这个表格记录了在给定成本的情况下背包的最佳配置。看起来你的想法有所不同。 - dragonxlwang