具有附加属性的背包算法

Question

当有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) - 记录编号1和记录编号3

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

(2) - 记录号码4

  3 4 5

因为第一组记录是最便宜的(4 <5),所以我们选择了它.不仅我要弄清楚这些记录是否存在,我还必须找到我总结的记录.

但就目前而言,我只需要了解,3d数组将如何显示.你们中的一些人可以帮我解决这个问题并逐层展示,就像我的形象一样,这会是什么样子？谢谢.

Answer 1

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

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