0
最近，我遇到了一个真正的问题，我可以refolmulate为以下算法任务的钱给量：是否有可能与给定的成本出售的所有项目，以人
问题：
给定一组N个人，每个人都有一定数额的金钱和一套M物品，每个物品都有一定的成本，是否有可能出售所有物品？
每件商品最多只能由一个人购买，每个人可以购买多件商品，以使其成本不超过他所拥有的金额。
我尝试的解决方案：
我想构建一个网络，找到一个最大流这样的方向：
- 使对应于人的一部分与顶点的bipartide图，而在其他部分 - 项目。
- 将人连接到源S，并将边缘容量设置为人们拥有的金钱。
- 将物品连接到水槽T并将边缘能力设置为物料成本。
- 连接每个人的项目，他可以购买和设置边缘能力的项目成本
在情况下，在最大流量每边在这个网络中发现要么是空的或完全饱和的，这个问题将通过寻找可以解决如果所有到T的边都是饱和的，并且如果我们想知道谁应该买什么物品，我们会看左边和右边部分之间的边缘。
但是，问题是，产生的流可以包含部分填充的边缘（意思是一个人部分支付一些项目），这种情况下，我无法消除。