多约束背包问题

Question

如果存在多个约束（例如，同时有体积限制和重量限制，其中每件物品的体积和重量不相关），我们得到多重约束背包问题、多维背包问题或 m维背包问题。

我如何以最优化的方式编码？好吧，我们可以开发一种强力递归解决方案。可能是分支定界..但本质上大多数时候它是指数级的，直到您进行某种记忆或使用动态编程，如果做得不好，这又会占用大量内存。

我面临的问题是

我有背包功能 KnapSack(Capacity, Value, i) 而不是常见的 KnapSack (Capacity, i) 因为我对这两个都有上限。谁能指导我这个吗？或者为相当大的 n 提供合适的资源来解决这些问题

，或者这个 NP 是否完整？

谢谢

Answer 1

合并约束。看看http://www.diku.dk/~pisinger/95-1.pdf
第 1.3.1 章称为“合并约束”。

一个例子是说你有
变量、约束 1、约束 2
1、43、66
2、65、54
3、34、49
4、99、32
5 , 2 , 88

将第一个约束乘以某个大数，然后将其添加到第二个约束。

所以你有
变量，合并约束
1、430066
2、650054
3、340049
4、990032
5 , 20088

从那里开始，用一个约束做任何你想做的算法。我想到的主要限制因素是变量可以容纳多少位数字。

Answer 2

一个很好的例子可以解决以下问题：

给定一个具有正权重和 N 个顶点的无向图 G。

你一开始有一笔M钱。为了经过一个顶点 i，你必须支付 S[i] 块钱。如果你没有足够的钱 - 你就无法通过那个顶点。考虑上述条件，找到从顶点 1 到顶点 N 的最短路径；或者声明这样的路径不存在。如果存在多条具有相同长度的路径，则输出最便宜的一条。限制：1

伪代码：

Set states(i,j) as unvisited for all (i,j)
Set Min[i][j] to Infinity for all (i,j)

Min[0][M]=0

While(TRUE)

Among all unvisited states(i,j) find the one for which Min[i][j]
is the smallest. Let this state found be (k,l).

If there wasn't found any state (k,l) for which Min[k][l] is
less than Infinity - exit While loop.

Mark state(k,l) as visited

For All Neighbors p of Vertex k.
   If (l-S[p]>=0 AND
    Min[p][l-S[p]]>Min[k][l]+Dist[k][p])
      Then Min[p][l-S[p]]=Min[k][l]+Dist[k][p]
   i.e.
If for state(i,j) there are enough money left for
going to vertex p (l-S[p] represents the money that
will remain after passing to vertex p), and the
shortest path found for state(p,l-S[p]) is bigger
than [the shortest path found for
state(k,l)] + [distance from vertex k to vertex p)],
then set the shortest path for state(i,j) to be equal
to this sum.
End For

End While

Find the smallest number among Min[N-1][j] (for all j, 0<=j<=M);
if there are more than one such states, then take the one with greater
j. If there are no states(N-1,j) with value less than Infinity - then
such a path doesn't exist.

Answer 3

有一些贪婪的启发式算法可以计算每个项目的“效率”，运行速度很快并产生近似解决方案。

您可以使用分支定界算法。您可以使用贪婪启发式获得初始下界，该下界可用于初始化现有解决方案。您可以通过一次考虑 m 个约束中的每一个（放宽问题中的其他约束）来计算各种子问题的上限，然后使用这些边界中的最低边界作为原始问题的上限。这项技术归功于施。然而，如果没有特定的约束倾向于主导解决方案，或者如果来自贪婪启发式的初始解决方案不接近最优，则该技术可能不会很好地工作。

有更好、更现代的算法，但更难实现，请参阅 J Puchinger 的“多维背包问题”论文！

Answer 4

正如您所说，体积和重量都是正数，请尝试使用重量总是减少的事实：

knap[position][vol][t]

现在，当 wt 为正数时，t=0，t=1 当 wt 为负数时。