算法:确定最小值/最大值的组合是否在给定范围内

Question

假设您有 3 个水桶，但每个水桶上都有一个洞。我正在尝试注满浴缸。浴缸有它需要的最低水位和它可以容纳的最高水位。当您拿着水桶到达浴缸时，您并不清楚水桶中会有多少水，但您有一系列可能的值。

是否可以将浴缸装满水？

您几乎有 3 个范围(最小值、最大值)，它们的总和是否会落在第 4 个范围内？

例如:桶 1 : 5-10L桶 2:15-25L三号桶:10-50L

浴缸100-150L

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

编辑:现在假设有 50 个不同的桶？

Answer 1

如果桶的容量不是很大(例如不大于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;
}

警告:代码未经测试