有n种物品可以放入背包，每种物品重量为wi和价值为vi，每种物品可以放多个，背包的最大重量限制是b,求使得背包价值最大的物品选择方案，利用分支限界法的思想解决下列问题： 1.该问题的代价函数如何设计？ 2.利用最大效益优先的方式进行遍历，写出算法的伪代码； 3.根据伪代码，写出matlab代码

1. 该问题的代价函数设计如下：对于每个节点，计算已经选择的物品的总重量和总价值，对于剩余的物品，估计其能够贡献的最大价值，将已经选择的总价值加上估计的最大价值，得到当前节点的价值。若当前节点的价值已经小于当前最优解，则剪枝。

2. 最大效益优先的方式进行遍历的伪代码如下：

initialize priority queue Q;
initialize current node u as the root of the search tree;
initialize the current upper bound as the total value of all items;
initialize the current best solution as an empty set;
while Q is not empty do
    u = Q.pop(); // choose node with highest priority
    if u is a leaf node then // check if the node is a solution
        if the value of u is greater than the current best solution then
            update the current best solution;
            update the current upper bound to the value of u;
    else if the value of u plus the estimated maximum value of the remaining items is greater than the current best solution then // check if it is worth exploring
        create child nodes by selecting the next item or not selecting the next item;
        calculate the estimated maximum value of each child node;
        add the child nodes to Q with priority based on their estimated maximum value;

3. 根据伪代码，可以编写如下的 MATLAB 代码：

% input data
n = 3; % number of item types
b = 50; % maximum weight of the knapsack
w = [10; 20; 30]; % weights of the items
v = [60; 100; 120]; % values of the items

% initialize priority queue
Q = PriorityQueue();
Q.push(Node(0, 0, 0, zeros(n, 1), ones(n, 1)));

% initialize current upper bound and best solution
ub = sum(v);
x_best = zeros(n, 1);
v_best = 0;

% search
while ~Q.isempty()
    % choose node with highest priority
    u = Q.pop();
    % check if the node is a solution
    if u.level == n
        if u.value > v_best
            v_best = u.value;
            x_best = u.x;
            ub = v_best;
        end
    % check if it is worth exploring
    elseif u.value + ub - u.estimate > v_best
        % create child nodes
        x = u.x;
        x(u.level+1) = 1;
        Q.push(Node(u.level+1, u.weight+w(u.level+1), u.value+v(u.level+1), x));
        x(u.level+1) = 0;
        Q.push(Node(u.level+1, u.weight, u.value, x));
        % calculate the estimated maximum value of each child node
        for i = 1:2
            child = Q.peek(i);
            weight = child.weight;
            estimate = child.value;
            for j = child.level+1:n
                if weight + w(j) <= b
                    weight = weight + w(j);
                    estimate = estimate + v(j);
                else
                    estimate = estimate + (b - weight) / w(j) * v(j);
                    break;
                end
            end
            Q.set_priority(i, estimate);
        end
    end
end

% output best solution
fprintf('Best value: %d\n', v_best);
fprintf('Best solution: ');
fprintf('%d ', x_best);
fprintf('\n');

其中，`PriorityQueue` 是优先队列类，`Node` 是搜索树节点类。