选择最小篮子数的算法策略

Question

例子:您有 4 个篮子，名称为 P、Q、R、S。您在名为 A、B、C、D 的篮子中有 4 件元素。

篮子的组成如下 PIC

--A B C D

P 6 4 0 7

问 6 4 1 1

R 4 6 3 6

小号 4 6 2 3

篮子 P 有 6A、4B、没有 C 和 7D。

假设您收到以下请求:你必须给出 10A、10B、3C 和 8D。

处理请求所需的最小篮子数量为 2 (P,R)。

我怎样才能通过算法达到这个目的。我应该使用什么算法，策略应该是什么？

Answer 1

像这样制作有向图(网络):

Source 具有 cost=1 和 capacity=bigvalue 的边到 P,Q,R,S 节点

P 有成本为 0 且容量为 6、4、7 的边到 A、B、D，其他篮子也一样。

A,B,C,D 有成本=0 和容量=10,10,3,8 的边下沉

现在解决Minimum-cost flow problem对于 10+10+3+8 流。