I'm trying to find an algorithm for the following problem.

There are $5$ computer files with capacity $18$, $23$, $12$, $125$, $45$ MB respectively and there are $4$ hard disks with capacity $25$, $73$, $38$, $156$ MB. Each file has to be saved in one and only one disk. The cost of saving a file $i$ in a disk $j$ is the capacity of the disk $j$. Find an algorithm of saving files such that the total cost is minimum.

I think this problem can be reformulated as the Min-cost-max-flow problem. However, I don't know how to refomulate the condition "the sum of capacity of files in a disk cannot exceed the capacity of that disk". Can anyone help me? Thank you very much.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.