具有 2 个属性的背包算法。如何在 3d 数组中实现它？

当有超过 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

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

将用动态规划求解1-约束背包问题的算法转换为求解2-约束问题是很容易的。对于某人来说，绘制 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)