Algorithmic Strategy for selection of minimum number of baskets

Question

Example: You have 4 baskets named P,Q,R,S. You have 4 items in those baskets named A,B,C,D.

The composition of baskets are as follows PIC

--A B C D

P 6 4 0 7

Q 6 4 1 1

R 4 6 3 6

S 4 6 2 3

Basket P has 6A, 4B, No C's and 7D.

Suppose you get following requests: You have to give out 10A, 10B, 3C and 8D.

The minimum number of basket required to process the request is 2 (P,R).

How can I reach this algorithmically. What algo should I use, what should be the strategy?

Answer 1

Make directed graph (network) like this:

Source has edges with cost=1 and capacity=bigvalue to P,Q,R,S nodes

P has edges with cost=0 and capacity 6,4,7 to A,B,D, same for other baskets.

A,B,C,D have edges with cost=0 and capacity=10,10,3,8 to sink

Now solve Minimum-cost flow problem for 10+10+3+8 flow.