2023-06-29 06:52 University of Edinburgh Java 发布于北京
关注
一个图优化问题-有点难度
给定一个矩阵A，aij表示货站i到需求点j的时间，如果aij=0则表示货站i不能前往需求点j。每次运输的货物不限量。不同货站间不能串货。货站与需求点之间直达。
例如一个矩阵A= [[1,2,3,5][2,4,6,8][3,5,6,3]] 表示时间，向量B=[3,3,1]表示1到3号货站的货物数量，向量C=[1,3,2,1]表示需求点1，2，3，4的货物需求量。
下面是必须满足的要求：
1. 对于每一个货站，累计送货时间尽可能短。
2. 只要存在通路，货站需要往尽量多的需求点运送货物。
3. 保证优先分配最近的需求点（每一个货站的运输总时间/每一个货站的运输次数达到最低）。
下面是可以尽量满足的要求：
1. 货站的货物不超额分配，或者最多超额5%。
2. 保证每一个需求点的需求，如果不可能，将不可实现的需求量降到最小。
求解：
1. 货物配送方式，以出发货站，目的地，运送货物量的形式输出。
备注：测试数据可能有问题。
备注：实际生产数据为1w个需求点，1k个货站。
#算法##图优化#
例如一个矩阵A= [[1,2,3,5][2,4,6,8][3,5,6,3]] 表示时间，向量B=[3,3,1]表示1到3号货站的货物数量，向量C=[1,3,2,1]表示需求点1，2，3，4的货物需求量。
下面是必须满足的要求：
1. 对于每一个货站，累计送货时间尽可能短。
2. 只要存在通路，货站需要往尽量多的需求点运送货物。
3. 保证优先分配最近的需求点（每一个货站的运输总时间/每一个货站的运输次数达到最低）。
下面是可以尽量满足的要求：
1. 货站的货物不超额分配，或者最多超额5%。
2. 保证每一个需求点的需求，如果不可能，将不可实现的需求量降到最小。
求解：
1. 货物配送方式，以出发货站，目的地，运送货物量的形式输出。
备注：测试数据可能有问题。
备注：实际生产数据为1w个需求点，1k个货站。
#算法##图优化#2023-06-29
在牛客打卡11天，今天也很努力鸭！
全部评论
wsq_star 楼主
楼主 University of Edinburgh Java
用贪心算法拿到了次优解
wsq_star 楼主
楼主 University of Edinburgh Java
订正：必须满足的需求有修改。应为1. 对于每一个货站，累计（送货时间*送货量）应尽可能小。
相关推荐
冷艳的柠檬精要暴富：二面怎么还问了这么多八股，还手写sql。还有代码题
查看16道真题和解析 点赞 评论 收藏
分享
点赞 评论 收藏
分享
2025-12-22 15:10
广西民族大学 算法工程师 点赞 评论 收藏
分享
点赞 评论 收藏
分享