多约束背包问题 [英] Multiple Constraint Knapsack Problem

问题描述

如果有一个以上的约束（例如，二者的体积限制和重量限制，其中每个项目的体积和重量是不相关的），我们得到的乘法受限背包问题，多维背包问题或m维背包问题。

If there is more than one constraint (for example, both a volume limit and a weight limit, where the volume and weight of each item are not related), we get the multiply-constrained knapsack problem, multi-dimensional knapsack problem, or m-dimensional knapsack problem.

我如何code这是最优化的方式？好了，我们可以开发出蛮力递归解决方案。可能是分支定界..但实际上它的指数大部分时间，直到你做一些记忆化，或使用动态编程而这又需要大量的内存，如果做得不好。

How do I code this in the most optimized fashion? Well, one can develop a brute force recursive solution. May be branch and bound.. but essentially its exponential most of the time until you do some sort of memoization or use dynamic programming which again takes a huge amount of memory if not done well.

我现在面临的问题是这样的

The problem I am facing is this

我有我的背包功能 背包（容量，价值，我），而不是常见的 背包（容量，I），因为我有这两个的上限。任何人都可以指导我吗？或提供适当的资源来解决这些问题，为合理的大的n

I have my knapsack function KnapSack( Capacity, Value, i) instead of the common KnapSack ( Capacity , i ) since I have upper limits on both of those. can anyone guide me with this? or provide suitable resources for solving these problems for reasonably large n

或者这是NP完全？

感谢

推荐答案

作为一个很好的例子就是服务于以下问题：

As a good example would serve the following problem:

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

Given an undirected graph G having positive weights and N vertices.

您开始具有m一笔钱。对于通过顶点我传球，你必须支付S [I]钱。如果你没有足够的钱 - 你不能通过顶点。查找到顶点n中的最短路径顶点1，遵守上述条件;或国家，这样的路径不存在。如果存在具有相同长度的多条路径，然后输出最便宜的。限制：1

伪code：

You start with having a sum of M money. For passing through a vertex i, you must pay S[i] money. If you don't have enough money - you can't pass through that vertex. Find the shortest path from vertex 1 to vertex N, respecting the above conditions; or state that such path doesn't exist. If there exist more than one path having the same length, then output the cheapest one. Restrictions: 1

Pseudocode:

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.

这篇关于多约束背包问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！