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

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

function [max_value, items] = knapsack(bag_size, weights, values)
    n = length(weights); % 物品数量
    queue = PriorityQueue(); % 优先队列，用于存储分支节点
    node = Node(0, 0, 0); % 根节点
    max_value = 0; % 最大价值
    items = zeros(1, n); % 最优解
    
    while ~isempty(node) % 队列非空
        if node.level == n % 叶子节点
            if node.value > max_value % 更新最优解
                max_value = node.value;
                items = node.items;
            end
        else % 非叶子节点
            % 计算左子树
            left_node = Node(node.level + 1, node.value, node.items);
            left_node.bound = bound(left_node, bag_size, weights, values);
            if left_node.bound > max_value % 可能成为最优解
                queue.add(left_node, left_node.bound);
            end
            
            % 计算右子树
            right_node = Node(node.level + 1, node.value + values(node.level + 1), node.items);
            right_node.items(node.level + 1) = 1;
            right_node.bound = bound(right_node, bag_size, weights, values);
            if right_node.bound > max_value % 可能成为最优解
                queue.add(right_node, right_node.bound);
            end
        end
        
        % 取出下一个节点
        [node, ~] = queue.pop();
    end
end

function b = bound(node, bag_size, weights, values)
    % 计算节点的上界
    if sum(weights(node.level+1:end)) <= bag_size - node.weight % 可以装下所有剩余物品
        b = node.value + sum(values(node.level+1:end));
    else % 只能装部分剩余物品
        b = node.value + (bag_size - node.weight) * values(node.level+1) / weights(node.level+1);
    end
end

classdef Node < handle
    % 分支节点类
    properties
        level % 节点层数
        value % 当前总价值
        weight % 当前总重量
        bound % 节点上界
        items % 当前选择的物品
    end
    
    methods
        function obj = Node(level, value, items)
            obj.level = level;
            obj.value = value;
            obj.weight = sum(items .* weights);
            obj.bound = 0;
            obj.items = items;
        end
    end
end

classdef PriorityQueue < handle
    % 优先队列类
    properties
        nodes % 节点列表
        bounds % 节点上界列表
    end
    
    methods
        function obj = PriorityQueue()
            obj.nodes = {};
            obj.bounds = [];
        end
        
        function add(obj, node, bound)
            % 添加节点
            n = length(obj.bounds);
            i = n + 1;
            while i > 1 && bound > obj.bounds((i-1)/2)
                obj.nodes{i} = obj.nodes{(i-1)/2};
                obj.bounds(i) = obj.bounds((i-1)/2);
                i = (i-1)/2;
            end
            obj.nodes{i} = node;
            obj.bounds(i) = bound;
        end
        
        function [node, bound] = pop(obj)
            % 取出节点
            node = obj.nodes{1};
            bound = obj.bounds(1);
            obj.nodes(1) = [];
            obj.bounds(1) = [];
            n = length(obj.bounds);
            i = 1;
            while i <= (n-1)/2
                j = i*2;
                if j+1 <= n && obj.bounds(j+1) > obj.bounds(j)
                    j = j+1;
                end
                if obj.bounds(j) > obj.bounds(i)
                    temp_node = obj.nodes{i};
                    temp_bound = obj.bounds(i);
                    obj.nodes{i} = obj.nodes{j};
                    obj.bounds(i) = obj.bounds(j);
                    obj.nodes{j} = temp_node;
                    obj.bounds(j) = temp_bound;
                    i = j;
                else
                    break;
                end
            end
        end
    end
end

代码解释：

- `knapsack` 函数是主函数，输入背包大小、物品重量和价值，输出最大价值和最优解（选择哪些物品）。
- `bound` 函数是计算节点的上界，输入节点、背包大小、物品重量和价值，输出节点的上界。
- `Node` 类是分支节点类，包含节点的层数、当前总价值、当前总重量、节点上界和当前选择的物品。
- `PriorityQueue` 类是优先队列类，用于存储分支节点，并按照节点上界从大到小排序。

使用示例：

bag_size = 10;
weights = [2 3 4 5];
values = [3 4 5 6];
[max_value, items] = knapsack(bag_size, weights, values);
fprintf('最大价值：%d\n', max_value);
fprintf('选择的物品：');
for i = 1:length(items)
    if items(i) == 1
        fprintf('%d ', i);
    end
end
fprintf('\n');

输出结果：

最大价值：11
选择的物品：2 3 

表示在背包大小为 10 的情况下，选择第 2 和第 3 个物品可以获得最大价值 11。