利用分支限界法解决背包问题（非零一背包），matlab代码

以下是利用分支限界法解决非零一背包问题的 MATLAB 代码：

function [max_val, best_items] = knapsack_bnb(values, weights, capacity)
% values: 物品价值数组
% weights: 物品重量数组
% capacity: 背包容量
% max_val: 背包能够装载的最大价值
% best_items: 背包能够装载的最优物品方案

n = length(values); % 物品数量
max_val = 0; % 最大价值
best_items = zeros(n, 1); % 最优物品方案

% 初始化根节点
root = struct('level', 0, 'value', 0, 'weight', 0, 'bound', 0, 'items', zeros(n, 1));

% 初始化最优物品方案的上界
ub = knapsack_greedy(values, weights, capacity, n);
% 初始化优先队列
pq = PriorityQueue();
pq.insert(root, ub);

while ~pq.isempty()
    % 取出优先队列中的最高优先级节点
    node = pq.pop();
    % 如果该节点的上界比当前最大价值小，则不需要继续扩展该节点
    if node.bound < max_val
        continue
    end
    % 如果该节点为叶子节点，则更新最大价值和最优物品方案
    if node.level == n
        if node.value > max_val
            max_val = node.value;
            best_items = node.items;
        end
        continue
    end
    % 扩展左儿子节点（选择该物品不放入背包）
    left = struct('level', node.level+1, 'value', node.value, 'weight', node.weight, 'bound', 0, 'items', node.items);
    left.bound = knapsack_bound(left, values, weights, capacity, n);
    if left.bound > max_val
        pq.insert(left, left.bound);
    end
    % 扩展右儿子节点（选择该物品放入背包）
    if node.weight+weights(node.level+1) <= capacity
        right = struct('level', node.level+1, 'value', node.value+values(node.level+1), ...
            'weight', node.weight+weights(node.level+1), 'bound', 0, 'items', node.items);
        right.bound = knapsack_bound(right, values, weights, capacity, n);
        if right.bound > max_val
            right.items(node.level+1) = 1;
            pq.insert(right, right.bound);
        end
    end
end

end

function bound = knapsack_bound(node, values, weights, capacity, n)
% 计算节点的上界
bound = node.value;
total_weight = node.weight;
i = node.level+1;
while i <= n && total_weight+weights(i) <= capacity
    total_weight = total_weight + weights(i);
    bound = bound + values(i);
    i = i + 1;
end
if i <= n
    bound = bound + (capacity-total_weight) .* values(i) ./ weights(i);
end
end

该代码首先利用贪心算法计算最优物品方案的上界，然后初始化根节点，并将根节点插入优先队列中。接着，从优先队列中取出最高优先级节点，如果该节点的上界比当前最大价值小，则不需要继续扩展该节点；如果该节点为叶子节点，则更新最大价值和最优物品方案；否则，扩展左儿子节点（选择该物品不放入背包）和右儿子节点（选择该物品放入背包），并将它们插入优先队列中。这个过程一直持续到优先队列为空。

需要注意的是，该算法的时间复杂度为 $O(2^n)$，因此只适用于物品数量较小的情况。另外，该算法使用了一个优先队列来存储节点，因此需要先下载 PriorityQueue 类的代码，并确保它在当前 MATLAB 的搜索路径中。