分支定界法matlab程序

以下是一个使用分支定界法求解二维背包问题的 Matlab 程序示例：

function [max_value, solution] = branch_and_bound_2Dknapsack(max_weight, weights, values)
% 使用分支定界法求解二维背包问题
% 输入参数：
%   max_weight: 背包最大重量
%   weights: 物品重量向量
%   values: 物品价值向量
% 输出参数：
%   max_value: 最大价值
%   solution: 最优解向量

n = length(weights); % 物品数量
visited = zeros(1, n); % 记录物品是否被访问过
upper_bound = upper_bound_2Dknapsack(max_weight, weights, values); % 计算上界

% 初始化搜索树根节点
root_node.level = 0;
root_node.weight = 0;
root_node.value = 0;
root_node.bound = upper_bound;
root_node.solution = [];

% 初始化最优解
max_value = 0;
solution = [];

% 初始化搜索栈
stack = [root_node];

while ~isempty(stack)
    % 取出栈顶节点
    node = stack(end);
    stack(end) = [];
    
    % 如果节点的界限小于当前最优解，则剪枝
    if node.bound <= max_value
        continue;
    end
    
    % 如果节点已经搜索到叶节点，则更新最优解
    if node.level == n
        if node.value > max_value
            max_value = node.value;
            solution = node.solution;
        end
        continue;
    end
    
    % 分别处理左儿子和右儿子
    item_weight = weights(node.level+1);
    item_value = values(node.level+1);
    % 处理左儿子
    left_node.level = node.level + 1;
    left_node.weight = node.weight;
    left_node.value = node.value;
    left_node.bound = bound_2Dknapsack(max_weight, weights, values, left_node.level, left_node.weight, left_node.value);
    left_node.solution = node.solution;
    % 如果左儿子可行，则加入搜索栈
    if left_node.bound > max_value && left_node.weight + item_weight <= max_weight
        left_node.weight = left_node.weight + item_weight;
        left_node.value = left_node.value + item_value;
        left_node.solution(end+1) = 1;
        stack(end+1) = left_node;
    end
    % 处理右儿子
    right_node.level = node.level + 1;
    right_node.weight = node.weight;
    right_node.value = node.value;
    right_node.bound = bound_2Dknapsack(max_weight, weights, values, right_node.level, right_node.weight, right_node.value);
    right_node.solution = node.solution;
    % 如果右儿子可行，则加入搜索栈
    if right_node.bound > max_value
        right_node.solution(end+1) = 0;
        stack(end+1) = right_node;
    end
end
end

function bound = bound_2Dknapsack(max_weight, weights, values, level, weight, value)
% 计算节点的界限
n = length(weights);
bound = value;
while level < n && weight + weights(level+1) <= max_weight
    weight = weight + weights(level+1);
    value = value + values(level+1);
    bound = bound + values(level+1);
    level = level + 1;
end
if level < n
    bound = bound + (max_weight - weight) * values(level+1) / weights(level+1);
end
end

function bound = upper_bound_2Dknapsack(max_weight, weights, values)
% 计算问题的上界
n = length(weights);
[sorted_values, idx] = sort(values ./ weights, 'descend');
weight = 0;
value = 0;
for i = 1:n
    if weight + weights(idx(i)) <= max_weight
        weight = weight + weights(idx(i));
        value = value + values(idx(i));
    else
        value = value + sorted_values(i) * (max_weight - weight);
        break;
    end
end
bound = value;
end

该程序定义了三个函数：

- `bound_2Dknapsack`：计算节点的界限。
- `upper_bound_2Dknapsack`：计算问题的上界。
- `branch_and_bound_2Dknapsack`：使用分支定界法求解二维背包问题。

其中，`branch_and_bound_2Dknapsack` 函数实现了分支定界法的主要逻辑，利用搜索栈不断扩展搜索树，直到搜索树被完全搜索或者找到了最优解。在每一步搜索中，程序通过计算节点的界限来决定是否需要剪枝，从而提高搜索效率。最终，程序输出最大价值和最优解向量。