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

1. 该问题的代价函数可以设计为当前已经选入的物品的总价值加上剩余物品的最大价值估计。其中剩余物品的最大价值估计可以通过将剩余物品按照单位重量的价值从大到小排序，然后依次将剩余空间填满，直到无法再放入为止，此时得到的总价值即为剩余物品的最大价值估计。

2. 最大效益优先的方式进行遍历，可以使用优先队列来实现。具体算法的伪代码如下：

initialize a priority queue Q
insert an empty state into Q
while Q is not empty do
  remove the state s with the highest priority from Q
  if s is a goal state then
    return s
  for each item i do
    if i can be added to s without exceeding the weight limit then
      create a new state s' by adding i to s
      if s' has a greater priority than the best solution found so far then
        insert s' into Q

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

function [max_value, selected_items] = knapsack(values, weights, capacity)
  n = length(values);
  selected_items = zeros(n, 1);
  max_value = 0;
  
  % sort items by unit value in descending order
  unit_values = values ./ weights;
  [~, sorted_indices] = sort(unit_values, 'descend');
  
  % initialize priority queue with empty state
  queue = PriorityQueue();
  queue.insert(struct('weight', 0, 'value', 0, 'items', selected_items, 'bound', 0));
  
  while ~queue.isempty()
    % remove state with highest priority from queue
    state = queue.pop();
    
    if state.bound < max_value
      % prune this state, as it cannot lead to a better solution
      continue;
    end
    
    if state.weight <= capacity && state.value > max_value
      % update best solution found so far
      max_value = state.value;
      selected_items = state.items;
    end
    
    if state.bound > max_value
      % generate child states by adding each item to the current state
      for i = 1:n
        j = sorted_indices(i);
        if state.weight + weights(j) <= capacity
          % add item j to the current state
          new_items = state.items;
          new_items(j) = new_items(j) + 1;
          
          % compute bound for the new state
          new_value = state.value + values(j);
          new_weight = state.weight + weights(j);
          remaining_capacity = capacity - new_weight;
          
          if i < n
            % estimate maximum value for remaining items using fractional knapsack
            remaining_values = unit_values(sorted_indices(i+1:end)) .* weights(sorted_indices(i+1:end));
            [~, idx] = sort(remaining_values, 'descend');
            remaining_values = remaining_values(idx);
            remaining_weights = weights(sorted_indices(i+1:end));
            remaining_weights = remaining_weights(idx);
            
            while remaining_capacity > 0 && ~isempty(remaining_weights)
              take = min(remaining_capacity, remaining_weights(1));
              new_value = new_value + take * unit_values(sorted_indices(i+1:end));
              remaining_capacity = remaining_capacity - take;
              remaining_weights(1) = remaining_weights(1) - take;
              if remaining_weights(1) == 0
                remaining_weights(1) = [];
                remaining_values(1) = [];
              end
            end
          end
          
          % add new state to the queue
          queue.insert(struct('weight', new_weight, 'value', new_value, 'items', new_items, 'bound', new_value + remaining_values(1)));
        end
      end
    end
  end
end