多约束背包问题

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

我如何以最优化的方式编码？ 那么，可以开发一个强力递归解决方案。 可能是分支和绑定..但基本上它的指数大部分时间，直到你做某种memoization或使用动态编程，如果做得不好，再次需要大量的内存。

我面临的问题是这样的

我有我的背包功能KnapSack（容量，价值，我），而不是普通的KnapSack（容量，我），因为我对这两者都有上限。 任何人都可以用这个指导我吗？ 或者提供合适的资源来解决这些问题

或者这个NP是否完整？

谢谢

---

合并约束。 看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

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

---

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

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

你从一笔M钱开始。 为了通过顶点我，你必须支付S [我]钱。 如果你没有足够的钱 - 你不能通过那个顶点。 根据上述条件查找从顶点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.

---

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

链接地址: http://www.djcxy.com/p/59939.html

上一篇: Multiple Constraint Knapsack Problem

下一篇: When Wifi disconnect, how does Socket on Android server side know that?