2

バケツが 3 つあるとしますが、それぞれに穴があります。浴槽に水をためようとしています。浴槽には必要最低限​​の水量と、入れることのできる最大水量があります。バケツを持って浴槽に到達するまでに、バケツにどれだけの水が入っているかは明確ではありませんが、可能な値の範囲はわかっています。

浴槽に水を十分に満たすことはできますか？

ほとんどの場合、3 つの範囲 (最小、最大) がありますが、それらの合計が 4 番目の範囲内に収まるものはありますか?

例: バケット 1 : 5 ～ 10L バケット 2 : 15 ～ 25L バケット 3 : 10 ～ 50L

バスタブ 100～150L

必要な範囲内で浴槽を満たす 1 2 と 3 の保証された組み合わせはありますか? 各バケットの倍数を使用できます。

編集: 50 の異なるバケットがあると想像してみてください。

4

7 に答える 7

1

浴槽の容量がそれほど大きくない場合 (例として 10^6 以下)、動的計画法を使用して解決できます。

アプローチ：

初期化: memo[X][Y] は結果を記憶する配列です。X = バケツの数、Y = 浴槽の最大容量。memo[][] を -1 で初期化します。

コード：

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

これが、最適なソリューション（バケットの最小数）を見つけるための私のソリューションです。最大値の比率と最小値の比率を比較して、浴槽を満たすバケツの最適な数を割り出します。

    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

これは、変更作成の問題を複数回適用することで解決できます。

各 Bucket.Min 値は通貨単位であり、Bathtub.Min はターゲット値です。

変更を行うアルゴリズムを介して解決策を見つけたら、もう 1 つの制約を適用します。

sum(ソリューション内の各 Bucket.Max) <= Bathtub.max

この制約が満たされない場合は、このソリューションを破棄して別のソリューションを探してください。これにはおそらく、標準の変更作成アルゴリズムを変更して、適切でないことが判明した場合に他のソリューションを試すことができるようにする必要があります。

于 2013-08-22T19:50:54.370 に答える
0

各バケツの「範囲」は、バケツに到達したときの水の量であり、気にするのは、バケツが一杯になる可能性があるかどうかだけであると言っていると仮定します...

各バケットの「最大」を取得して合計するだけです。それが浴槽が「満たされている」と考える範囲内であれば、それは可能です。

于 2013-08-21T23:46:16.270 に答える