17

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

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

我面临的问题是这个

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

还是这个NP完整？

谢谢

4

5 回答 5

6

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

一个例子是说你有
variable , constraint1 , constraint2
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

从那里做任何你想用一个约束做的算法。想到这个变量可以容纳多少位数的主要限制器。

于 2014-02-05T03:16:01.877 回答
4

作为一个很好的例子将解决以下问题：

给定一个具有正权重和 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.
于 2009-12-16T06:36:36.037 回答
2

具有多个约束的背包是一个包装问题。阅读。 http://en.wikipedia.org/wiki/Packing_problem

于 2009-12-01T18:06:12.290 回答
0

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

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

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

于 2017-04-24T12:30:41.067 回答
-3

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

knap[position][vol][t]

现在t=0什么时候wt是积极的，t=1什么时候wt是消极的。

于 2016-08-21T18:06:42.533 回答