Algorithm: Determine if a combination of min/max values fall within a given range

Question

Imagine you have 3 buckets, but each of them has a hole in it. I'm trying to fill a bath tub. The bath tub has a minimum level of water it needs and a maximum level of water it can contain. By the time you reach the tub with the bucket it is not clear how much water will be in the bucket, but you have a range of possible values.

Is it possible to adequately fill the tub with water?

Pretty much you have 3 ranges (min,max), is there some sum of them that will fall within a 4th range?

For example: Bucket 1 : 5-10L Bucket 2 : 15-25L Bucket 3 : 10-50L

Bathtub 100-150L

Is there some guaranteed combination of 1 2 and 3 that will fill the bathtub within the requisite range? Multiples of each bucket can be used.

EDIT: Now imagine there are 50 different buckets?

Answer 1

Here is my solution for finding the optimal solution (least number of buckets). It compares the ratio of the maximums to the ratio of the minimums, to figure out the optimal number of buckets to fill the tub.

    private static void BucketProblem()
    {
        Range bathTub = new Range(100, 175);

        List<Range> buckets = new List<Range> {new Range(5, 10), new Range(15, 25), new Range(10, 50)};

        Dictionary<Range, int> result;
        bool canBeFilled = SolveBuckets(bathTub, buckets, out result);
    }

    private static bool BucketHelper(Range tub, List<Range> buckets, Dictionary<Range, int> results)
    {
        Range bucket;
        int startBucket = -1;
        int fills = -1;
        for (int i = buckets.Count - 1; i >=0 ; i--)
        {
            bucket = buckets[i];
            double maxRatio = (double)tub.Maximum / bucket.Maximum;
            double minRatio = (double)tub.Minimum / bucket.Minimum;
            if (maxRatio >= minRatio)
            {
                startBucket = i;
                if (maxRatio - minRatio > 1)
                    fills = (int) minRatio + 1;
                else
                    fills = (int) maxRatio;
                break;
            }
        }          

        if (startBucket < 0)
            return false;
        bucket = buckets[startBucket];

        tub.Maximum -= bucket.Maximum * fills;
        tub.Minimum -= bucket.Minimum * fills;
        results.Add(bucket, fills);

        return tub.Maximum == 0 || tub.Minimum <= 0 || startBucket == 0 || BucketHelper(tub, buckets.GetRange(0, startBucket), results);
    }

    public static bool SolveBuckets(Range tub, List<Range> buckets, out Dictionary<Range, int> results)
    {
        results = new Dictionary<Range, int>();
        buckets = buckets.OrderBy(b => b.Minimum).ToList();
        return BucketHelper(new Range(tub.Minimum, tub.Maximum), buckets, results); 
    }

Answer 2

Initially, your target range is Bathtub.Range.

Each time you add an instance of a bucket to the solution, you reduce the target range for the remaining buckets.

For example, using your example buckets and tub:

Target Range = 100..150

Let's say we want to add a Bucket1 to the candidate solution. That then gives us

Target Range = 95..140

because if the rest of the buckets in the solution total < 95, then this Bucket1 might not be sufficient to fill the tub to 100, and if the rest of the buckets in the solution total > 140, then this Bucket1 might fill the tub over 150.

So, this gives you a quick way to check if a candidate solution is valid:

TargetRange = Bathtub.Range
foreach Bucket in CandidateSolution
  TargetRange.Min -= Bucket.Min
  TargetRange.Max -= Bucket.Max
  if TargetRange.Min == 0 AND TargetRange.Max >= 0 then solution found
  if TargetRange.Min < 0 or TargetRange.Max < 0 then solution is invalid

This still leaves the question - How do you come up with the set of candidate solutions?

Brute force would try all possible combinations of buckets.

Answer 3

This can be solved with multiple applications of the change making problem.

Each Bucket.Min value is a currency denomination, and Bathtub.Min is the target value.

When you find a solution via a change-making algorithm, then apply one more constraint:

sum(each Bucket.Max in your solution) <= Bathtub.max

If this constraint is not met, throw out this solution and look for another. This will probably require a change to a standard change-making algorithm that allows you to try other solutions when one is found to not be suitable.

Answer 4

Updated:

Given that buckets can be used multiple times, this seems to me like we're looking for solutions to a pair of equations.

Given buckets x, y and z we want to find a, b and c:

a*x.min + b*y.min + c*z.min >= bathtub.min

and

a*x.max + b*y.max + c*z.max <= bathtub.max

Re: http://en.wikipedia.org/wiki/Diophantine_equation

If bathtub.min and bathtub.max are both multiples of the greatest common divisor of a,b and c, then there are infinitely many solutions (i.e. we can fill the tub), otherwise there are no solutions (i.e. we can never fill the tub).

Answer 5

Here's a naïve recursive solution in python that works just fine (although it doesn't find an optimal solution):

def match_helper(lower, upper, units, least_difference, fail = dict()):
  if upper < lower + least_difference:
    return None
  if fail.get((lower,upper)):
    return None
  exact_match = [ u for u in units if u['lower'] >= lower and u['upper'] <= upper ]
  if exact_match:
    return [ exact_match[0] ]

  for unit in units:
    if unit['upper'] > upper:
      continue
    recursive_match = match_helper(lower - unit['lower'], upper - unit['upper'], units, least_difference)
    if recursive_match:
      return [unit] + recursive_match
  else:
    fail[(lower,upper)] = 1
    return None

def match(lower, upper):
  units = [
      { 'name': 'Bucket 1', 'lower': 5,  'upper': 10 },
      { 'name': 'Bucket 2', 'lower': 15, 'upper': 25 },
      { 'name': 'Bucket 3', 'lower': 10, 'upper': 50 }
  ]

  least_difference = min([ u['upper'] - u['lower'] for u in units ])
  return match_helper(
    lower = lower,
    upper = upper,
    units = sorted(units, key = lambda u: u['upper']),
    least_difference = min([ u['upper'] - u['lower'] for u in units ]),
  )

result = match(100, 175)
if result:
  lower = sum([ u['lower'] for u in result ])
  upper = sum([ u['upper'] for u in result ])
  names = [ u['name'] for u in result ]
  print lower, "-", upper
  print names
else:
  print "No solution"

It prints "No solution" for 100-150, but for 100-175 it comes up with a solution of 5x bucket 1, 5x bucket 2.

Answer 6

If the capacity of the tub is not very large ( not greater than 10^6 for an example), we can solve it using dynamic programming.

Approach:

Initialization: memo[X][Y] is an array to memorize the result. X = number of buckets, Y = maximum capacity of the tub. Initialize memo[][] with -1.

Code:

bool dp(int bucketNum, int curVolume){

    if(curVolume > maxCap)return false;             // pruning extra branches

    if(curVolume>=minCap && curVolume<=maxCap){     // base case on success
        return true;
    }

    int &ret = memo[bucketNum][curVolume];
    if(ret != -1){                                  // this state has been visited earlier
        return false;
    }
    ret = false;

    for(int i = minC[bucketNum]; i < = maxC[bucketNum]; i++){
        int newVolume = curVolume + i;
        for(int j = bucketNum; j <= 3; j++){
            ret|=dp(j,newVolume);
            if(ret == true)return ret;
        }
    }
    return ret;
}

Warning: Code not tested

Answer 7

Assuming you are saying that the "range" for each bucket is the amount of water that it may have when it reaches the tub, and all you care about is if they could possibly fill the tub...

Just take the "max" of each bucket and sum them. If that is in the range of what you consider the tub to be "filled" then it can.