贪心算法的Matlab实现代码

以下是贪心算法的 Matlab 实现代码：

function [selected_items, total_value] = greedy_algorithm(values, weights, capacity)
% values: 物品价值数组
% weights: 物品重量数组
% capacity: 背包的容量

n_items = length(values);
selected_items = zeros(1, n_items);
total_weight = 0;
total_value = 0;

% 按照物品的单位价值排序
unit_values = values ./ weights;
[~, sorted_idx] = sort(unit_values, 'descend');

% 选择单位价值最高的物品，直到不能再添加为止
for i = 1:n_items
    item_idx = sorted_idx(i);
    if total_weight + weights(item_idx) <= capacity
        selected_items(item_idx) = 1;
        total_weight = total_weight + weights(item_idx);
        total_value = total_value + values(item_idx);
    end
end

end

使用示例：

values = [60, 100, 120];
weights = [10, 20, 30];
capacity = 50;

[selected_items, total_value] = greedy_algorithm(values, weights, capacity);
disp(selected_items); % [1, 1, 0]
disp(total_value); % 160

注意，贪心算法并不能保证一定得到最优解，但它的时间复杂度较低，适用于某些特定的背包问题。