算法设计-分支界限法--装载问题

装载问题是指在给定的一批集装箱中选取若干个装上一艘载重量为C的轮船，如何才能使装上的集装箱重量最大。这是一个NP完全问题，可以使用分支限界法来解决。

分支限界法是一种用于求解最优化问题的通用算法。它通过将问题的解空间划分为若干个子集，每个子集对应一个可行解，然后通过限制条件和目标函数来剪枝，从而逐步缩小搜索空间，最终找到最优解。

下面是使用队列式分支限界法求解装载问题的Python代码：

import queue

class Node:
    def __init__(self, level, weight, value, bound):
        self.level = level
        self.weight = weight
        self.value = value
        self.bound = bound

def bound(node, n, c, w, v):
    if node.weight >= c:
        return 0
    else:
        bound = node.value
        j = node.level + 1
        totweight = node.weight
        while j < n and totweight + w[j] <= c:
            totweight += w[j]
            bound += v[j]
            j += 1
        if j < n:
            bound += (c - totweight) * v[j] / w[j]
        return bound

def knapsack(n, c, w, v):
    q = queue.Queue()
    u = Node(-1, 0, 0, 0)
    v = Node(-1, 0, 0, bound(u, n, c, w, v))
    maxvalue = 0
    q.put(v)
    while not q.empty():
        u = q.get()
        if u.bound > maxvalue:
            i = u.level + 1
            u1 = Node(i, u.weight + w[i], u.value + v[i], 0)
            if u1.weight <= c and u1.value > maxvalue:
                maxvalue = u1.value
            u1.bound = bound(u1, n, c, w, v)
            if u1.bound > maxvalue:
                q.put(u1)
            u2 = Node(i, u.weight, u.value, 0)
            u2.bound = bound(u2, n, c, w, v)
            if u2.bound > maxvalue:
                q.put(u2)
    return maxvalue

w = [90, 80, 40, 30, 20, 12, 10]
v = [90, 80, 40, 30, 20, 12, 10]
c = 152
n = len(w)
print("最大装载重量为：", knapsack(n, c, w, v))