开源众包
420人浏览/13人投稿
637天前
已托管赏金
需要熟悉网络流和最大流最小割问题问题描述：一个产品由不同的模块组成，每个模块有不同的模块型号，一个产品需要在每个模块中选择一个型号进行组装，形成最后的产品。需要建立一个从产品到模块的网络图，定义网络图中的边具有多个属性，多层级的属性（成本和需求），最后使用最大流最小割算法求解网络图，权衡不同属性流之间的关系，目标是能够缩减每种模块的型号，从而达成以最少型号的模块组合能够覆盖最多的订单（也就是产品）。数据有了，算法的框架也有，根据框架把内容写出来就行。代码的框架第一步：导入数据，导入产品和模块的不同数据第二步：建立网络图1） 建立从源点出发到产品节点的关系2） 建立从产品节点到模块节点的关系注意，不同产品可能会使用一种模块下面的同一型号的模块，同一型号模块节点应该唯一；同时因为不是所有的产品都是产成品，有些产品是半成品，所以不是所有产品都会链接到所有的16种模块下面，产品只需要链接到它包含的模块即可3）建立模块节点到汇点的关系第三步：赋予网络图中的边不同属性流第一层属性流是数量关系，根据所给出的产品的需求数据可以推出每个产品以及每个模块的数量要求第二层属性流是成本关系，根据每个模块的成本可以推出产品的总成本第四步：应用最大流最小割算法可以参考最小成本最大流算法等，此处采用的算法不做要求，可以给参考文献网络图中，同一型号的模块应该用同一种颜色进行区分，同时源点、汇点和产品节点也应该用不同颜色进行区分第五步：输出算法运行结果，输出最初的网络图以及经过优化后的网络图最后的成果：1，建立好的网络图，2，优化后的结果3，代码
