2

想象一下，你有 3 个桶，但每个桶里都有一个洞。我正试图填满浴缸。浴缸有它需要的最低水位和它可以容纳的最高水位。当您带着桶到达浴缸时，尚不清楚桶中有多少水，但您有一系列可能的值。

是否可以将水充分装满浴缸？

几乎你有 3 个范围（最小，最大），它们的总和会落在第 4 个范围内吗？

例如： 1号桶：5-10L 2号桶：15-25L 3号桶：10-50L

浴缸 100-150L

是否有一定的 1 2 和 3 组合可以在必要范围内填充浴缸？每个桶可以使用多个。

编辑：现在想象有 50 个不同的桶？

4

7 回答 7

1

这是 python 中一个简单的递归解决方案，它工作得很好（尽管它没有找到最佳解决方案）：

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"

它为 100-150 打印“无解决方案”，但对于 100-175，它提供了 5x 桶 1、5x 桶 2 的解决方案。

于 2013-08-22T01:20:59.043 回答
1

如果 tub 的容量不是很大（例如不大于 10^6），我们可以使用动态规划来解决。

方法：

初始化： memo[X][Y] 是一个数组，用来记忆结果。X = 桶数，Y = 桶的最大容量。用 -1 初始化 memo[][]。

代码：

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;
}

警告：代码未经测试

于 2013-08-22T01:13:25.510 回答
0

更新：

鉴于桶可以多次使用，在我看来，这就像我们正在寻找一对方程的解。

给定桶 x、y 和 z，我们想要找到 a、b 和 c：

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

和

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

回复：http ://en.wikipedia.org/wiki/Diophantine_equation

如果 bathtub.min 和 bathtub.max 都是 a、b 和 c 的最大公约数的倍数，则有无穷多个解（即我们可以填满浴缸），否则没有解（即我们永远无法填满浴缸）浴缸）。

于 2013-08-21T23:54:20.540 回答
0

假设您说每个桶的“范围”是它到达浴缸时可能含有的水量，而您所关心的只是它们是否可以装满浴缸......

只需取每个桶的“最大值”并将它们相加即可。如果这在您认为浴缸被“填充”的范围内，那么它可以。

于 2013-08-21T23:46:16.270 回答
0

这可以通过改变制造问题的多种应用来解决。

每个 Bucket.Min 值是货币面额，Bathtub.Min 是目标值。

当您通过更改算法找到解决方案时，再应用一个约束：

总和（解决方案中的每个 Bucket.Max）<= Bathtub.max

如果不满足此约束，请丢弃此解决方案并寻找另一个解决方案。这可能需要更改标准的更改算法，以便在发现不适合时尝试其他解决方案。

于 2013-08-22T19:50:54.370 回答
0

这是我寻找最佳解决方案（最少桶数）的解决方案。它将最大值与最小值的比率进行比较，以确定填充桶的最佳桶数。

    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); 
    }
于 2013-08-22T21:00:34.737 回答
0

最初，您的目标范围是 Bathtub.Range。

每次将存储桶的实例添加到解决方案时，都会减少剩余存储桶的目标范围。

例如，使用您的示例存储桶和浴缸：

目标范围 = 100..150

假设我们想将 Bucket1 添加到候选解决方案中。那给了我们

目标范围 = 95..140

因为如果解决方案中的其余桶总数 < 95，则此 Bucket1 可能不足以将桶装满 100，如果解决方案中的其余桶总数 > 140，则此桶 1 可能会将桶装满150。

因此，这为您提供了一种快速检查候选解决方案是否有效的方法：

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

这仍然留下了一个问题 - 您如何提出一组候选解决方案？

蛮力将尝试所有可能的桶组合。

于 2013-08-22T17:45:23.547 回答