贪心算法MATLAB代码

### 贪婪算法的MATLAB实现

贪婪算法是一种通过一系列局部最优解的选择来构建全局近似最优解的方法。下面提供了一个简单的贪婪算法实例，用于解决0/1背包问题，在给定物品重量和价值的情况下最大化总价值。

function [selectedItems, totalValue] = greedyKnapsack(weights, values, capacity)
    % 计算每项的价值密度
    n = length(values);
    valueDensity = zeros(n, 1);
    
    for i = 1:n
        valueDensity(i) = values(i) / weights(i);
    end
    
    % 将项目按价值密度降序排列
    [~, idx] = sort(valueDensity, 'descend');
    sortedWeights = weights(idx);
    sortedValues = values(idx);

    selectedItems = false(1, n); % 初始化选择状态数组
    remainingCapacity = capacity;
    totalValue = 0;

    for i = 1:n
        if remainingCapacity >= sortedWeights(i)
            selectedItems(idx(i)) = true;     % 添加到已选列表
            remainingCapacity = remainingCapacity - sortedWeights(i);
            totalValue = totalValue + sortedValues(i);
        else
            break; % 如果当前物品无法放入，则停止循环
        end
    end
end

此函数`greedyKnapsack`接收三个参数：物品权重向量`weights`、对应的价值向量`values`以及背包容量`capacity`。返回两个输出变量——布尔型向量`selectedItems`表示哪些物品被选取；数值`totalValue`代表所获得的最大化总价值[^1]。