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

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

function [max_value, best_solution] = knapsack_bnb(values, weights, capacity)
    n = length(values);
    best_solution = zeros(1, n);
    nodes = struct('level',0,'profit',0,'weight',0,'bound',0,'vector',zeros(1,n));
    queue = nodes; front = 1; back = 2;
    max_value = 0;
    
    % 节点排序函数
    cmp = @(a,b) (a.bound > b.bound || (a.bound == b.bound && a.level < b.level));
    
    % 初始化根节点
    nodes(1).level = 1;
    nodes(1).vector = zeros(1, n);
    nodes(1).bound = compute_bound(values, weights, capacity, nodes(1));
    
    while front < back
        % 取出队首节点
        node = queue(front); front = front + 1;
        
        % 判断是否要扩展该节点
        if node.bound > max_value
            % 扩展左儿子节点：不放当前物品
            left = struct('level',node.level+1,'vector',node.vector,'profit',node.profit,'weight',node.weight,'bound',0);
            left.vector(node.level) = 0;
            left.bound = compute_bound(values, weights, capacity, left);
            if left.bound > max_value
                queue(back) = left; back = back + 1;
                if left.bound == left.profit && left.profit > max_value
                    max_value = left.profit;
                    best_solution = left.vector;
                end
            end
            
            % 扩展右儿子节点：放当前物品
            right = struct('level',node.level+1,'vector',node.vector,'profit',node.profit,'weight',node.weight,'bound',0);
            right.vector(node.level) = 1;
            right.weight = node.weight + weights(node.level);
            right.profit = node.profit + values(node.level);
            right.bound = compute_bound(values, weights, capacity, right);
            if right.bound > max_value
                queue(back) = right; back = back + 1;
                if right.bound == right.profit && right.profit > max_value
                    max_value = right.profit;
                    best_solution = right.vector;
                end
            end
        end
        
        % 节点按照限界值和层数排序，以便优先扩展限界大的节点
        queue(front:back-1) = sort(queue(front:back-1), cmp);
    end
end

% 计算节点的限界值
function bound = compute_bound(values, weights, capacity, node)
    bound = node.profit;
    weight = node.weight;
    level = node.level;
    n = length(values);
    while level <= n && weight + weights(level) <= capacity
        bound = bound + values(level);
        weight = weight + weights(level);
        level = level + 1;
    end
    if level <= n
        bound = bound + (capacity - weight) * values(level) / weights(level);
    end
end

使用方法：

values = [10, 40, 30, 50];
weights = [5, 4, 6, 3];
capacity = 10;
[max_value, best_solution] = knapsack_bnb(values, weights, capacity);
disp(max_value); % 输出最大价值
disp(best_solution); % 输出最优解

其中 `values` 是每件物品的价值，`weights` 是每件物品的重量，`capacity` 是背包容量。函数返回最大价值和最优解，其中最优解是一个长度为 `n` 的 0/1 向量，表示每件物品是否放入背包。