用分支限界法解决背包问题 matlab代码

以下是用MATLAB实现分支限界法解决背包问题的示例代码：

% 背包问题分支限界法
clear;clc;

% 物品数量
n = 5;

% 物品重量和价值
w = [2, 3, 4, 5, 9];
v = [3, 4, 5, 8, 10];

% 背包容量
W = 20;

% 初始化最优解
best_x = zeros(1, n);

% 初始化当前节点的状态
node.x = zeros(1, n);
node.w = 0;
node.v = 0;
node.bound = 0;

% 初始化队列
queue = node;

% 分支限界法
while ~isempty(queue)
    % 取出队首节点
    node = queue(1);
    queue(1) = [];
    
    % 计算当前节点的上界
    k = find(node.x == 0, 1);
    while ~isempty(k)
        node.w = node.w + w(k);
        node.v = node.v + v(k);
        if node.w <= W
            node.bound = node.bound + v(k);
            k = find(node.x == 0, 1);
        else
            node.bound = node.bound + (W - node.w + w(k)) * v(k) / w(k);
            break;
        end
    end
    
    % 如果当前节点的上界比当前最优解小，则剪枝
    if node.bound <= sum(best_x .* v)
        continue;
    end
    
    % 如果当前节点已经到达叶子节点，则更新最优解
    if isempty(k)
        best_x = node.x;
        continue;
    end
    
    % 拆分新节点
    left.x = node.x;
    left.x(k) = 0;
    right.x = node.x;
    right.x(k) = 1;
    queue(end+1) = left;
    queue(end+1) = right;
end

% 输出结果
fprintf('最优解为：');
disp(best_x);
fprintf('最大价值为：%d\n', sum(best_x .* v));

该代码实现了一个简单的背包问题，将物品分为取和不取两个状态，依次计算每个状态的上界，从而确定下一步需要拆分的节点。在代码运行完毕后，输出最优解和最大价值。