Proving a set of requirements can be met with a set of values using LINQ

Question

This is a subset of the question posted here.

Given a set of buckets of volume B={x1, x2, ..., xn} and a set of vials with liquid of volumes V={v1, v2, ..., vn } what is the best way to prove that the number of buckets can be filled with the contents of the vials assuming that vials must be poured all into one bucket. Overflow is permitted.

Some obvious invariants here are that the cardinality of the buckets |B| must be less than or equal to the cardinality of the vials |V| and that the combined volume of the buckets Sum(B) must be less than or equal to the combined volume of the vials Sum(V)

Is this a well known computational problem? If so can a simple LINQ solution be crafted to express this in C#?

I feel like this is something Eric Lippert would have blogged about ;-).

Answer 1

Consider an instance of this problem where you have two buckets of the same size, and Sum(B) = Sum(V). This means you need to distribute the vials equally over the two buckets, otherwise one will overflow and there won't be enough left for the other. This is called the partition problem, and it is known to be NP-complete.

Edit: Of course, NP-completeness doesn't mean the problem can't be solved, just that the running time will be exponential in the size of the input (in this case, the log2 of the biggest bucket size).

If we can find the smallest amount of liquid needed to fill a bucket (including spillage), solving the problem is a simple matter of doing this for each bucket, and removing the used vials from the set of available vials after each bucket.

We can do this by using dynamic programming:

• For a given bucket b, consider all the buckets of size 0 up to volume(b).
• The size 0 bucket obviously requires no liquid
• For each size s, find a vial v such that:
  • The solution for s-volume(v) does not use v
  • (The amount of liquid used for s-volume(v)) + volume(v) is minimized
• At the end of all this you will have the vials used to fill bucket b. Then you just remove those from the set of available vials, and move on to the next bucket.