这个问题可否用二分图处理？
<P>有一个问题是这样的 ：</P><P>一个工程包括多个独立项目，每个项目都已经有了固定拨款值，工人每个人可以做一个或者多个项目，对应关系由矩阵表示，已知。而且假设项目很容易，如果选择了一个工人，那他就会将所有自己能做的项目做完。每个工人的工资数目已知（与他会做的工程多少无关，是个固定值） 。要求在每个项目都不超出固定拨款的情况下，求最小的开销，完成这个工程。</P>
<P>这个问题应该 用什么方法处理？</P> <P>首先考虑了用最优化方法，0/1枚举 ，但是效率太低。</P>
<P>考虑 到这个问题跟二分图中的带权最小覆盖有相似的地方，是否可以用二分图处理？如果可以的话应该怎么证明可行？</P>
页:
[1]