多约束背包问题

Question

如果存在多个约束(例如,体积限制和重量限制,每个项目的体积和重量都不相关),我们会得到多重约束的背包问题,多维背包问题或者m - 三维背包问题.

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

我面临的问题是这个

我有我的背包功能KnapSack(容量,价值,i)而不是常见的KnapSack(容量,i),因为我对这两者都有上限.任何人都可以指导我吗？或提供合适的资源来解决相当大的n的这些问题

或者这个NP是完整的吗？

谢谢

Answer 1

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

一个例子是说你有
可变,constraint1,constraint2
1,43,66
2,65%,54
3,34,49
4,99,32
5,2,88

将第一个约束乘以一些大数,然后将其添加到第二个约束.

所以你有
变量,合并约束
1,430066
2,65004
3,340049
4,990032
5,200888

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

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.