口罩分配优化算法 - 基于距离和需求的分配策略

该算法以多个家庭的口罩需求和地理位置信息为输入，通过计算每个家庭的口罩需求差值，并结合家庭之间的距离，采用贪婪算法进行口罩分配，最终使得所有家庭的口罩需求尽可能满足，并找到距离最短的两个家庭。

算法步骤：

1. 输入数据

   data = [1 18 12 14 15; ... 20 7 42 13 18];

   其中，每行代表一个家庭，包含家庭编号、人口数量、已拥有口罩数量、所需口罩数量、实际口罩数量。

2. 计算需求差值

   diffneed = data(:, 4) - data(:, 5);

   计算每个家庭所需口罩数量与实际口罩数量的差值。

3. 计算家庭之间的距离

   dist = pdist(data(:, 2:5), 'euclidean');

   使用欧氏距离计算每个家庭之间的距离。

4. 构建邻接矩阵

   adj = zeros(n);

   创建一个邻接矩阵，用于存储家庭之间的距离。

5. 查找需求差值为负的家庭

   neg_idx = find(diffneed < 0);

   找出需求差值为负的家庭，表示这些家庭需要借口罩。

6. 按需求差值排序

   [~, sort_idx] = sort(diffneed(neg_idx), 'descend');

   按照需求差值从大到小的顺序对需要借口罩的家庭进行排序。

7. 从需求差值为正的家庭中选择距离最近的家庭

   for i = 1:length(neg_idx)

   循环遍历每个需要借口罩的家庭，从需求差值为正的家庭中选择距离最近的家庭进行借用。

8. 调整需求差值

   diffneed(pos_idx) = diffneed(pos_idx) - abs(diffneed(idx));

   diffneed(idx) = 0;

   调整借用家庭和被借家庭的需求差值，使得借用家庭的需求差值变为 0。

9. 使用 Floyd 算法计算最短路径

   for k = 1:n

   循环遍历所有家庭，使用 Floyd 算法更新邻接矩阵，计算所有家庭之间的最短路径。

10. 找到距离最短的两个家庭

[min_dist, idx] = min(adj(:));

[row, col] = ind2sub([n,n], idx);

找出邻接矩阵中距离最小的两个家庭，并输出其编号和距离。

输出结果：

距离最短的两个家庭为 16 和 20，距离为 5.000000。

总结：

该算法通过计算每个家庭的口罩需求差值和家庭之间的距离，实现了高效的口罩分配策略，使得所有家庭的口罩需求尽可能满足，同时找到距离最短的两个家庭，方便后续的口罩传递。