已知一个固定容量的背包c=8和3个物品,每个物品有其重量和价值,重量分别为(2,7,1),价值分别为(1,9,3)。如果每个物品只能拿1个或不拿,请利用优先队列式分支限界法求不超过背包容量的前提下可获得的最大价

值。

首先，我们可以将物品按照价值比重量的比例从大到小排序，得到(2,1)，(7,9)，(1,3)。然后，我们可以定义一个状态节点，包括当前的重量和当前的价值。初始时，重量为0，价值为0。接着，我们维护一个优先队列，每次从队列中取出一个状态节点进行扩展，分别考虑取当前物品和不取当前物品两种情况。

对于取当前物品的情况，如果加上当前物品的重量不超过背包容量，则可以得到一个新的状态节点，该节点的重量是当前状态节点的重量加上当前物品的重量，价值是当前状态节点的价值加上当前物品的价值。将该新的状态节点加入优先队列中。

对于不取当前物品的情况，直接将当前状态节点加入优先队列中即可。

在优先队列中，我们按照价值最大的节点排在前面，所以每次取出的节点一定是当前可扩展节点中价值最大的。如果当前可扩展节点的价值加上剩余物品的最大价值仍然小于当前最优解，则可以剪枝，不进行扩展。

最终，当队列为空时，得到的最大价值就是可获得的最大价值。在这个例子中，可获得的最大价值为12。