algorithm - N個のケーキをM人に分けて無駄を最小限にする

Question

だからここに質問があります：

あるパーティーには、それぞれボリューム V1、V2、V3 ... Vn の n 個の異なるフレーバーのケーキがあります。パーティーに参加している K 人にそれらを分割する必要があります。

パーティーのメンバー全員が同じ量のケーキを手に入れます (たとえば、V が探しているソリューションです)。
各メンバーは、1 つのフレーバーのケーキのみを受け取る必要があります (異なるフレーバーのケーキの一部をメンバーに配布することはできません)。
ケーキの一部は配布後に廃棄されます。廃棄物を最小限に抑えたいと考えています。または、同等に、最大配布ポリシーを求めています

既知の条件が与えられた場合: V が最適解である場合、少なくとも 1 つのケーキ X は、体積を残さずに V で割ることができます。つまり、Vx mod V == 0 です。

最適な時間の複雑さを備えたソリューションを探しています (力ずくで解決できますが、より迅速な方法が必要です)。

任意の提案をいただければ幸いです。

ありがとう

PS: これは宿題ではなく、面接の質問です。ブルートフォースの疑似コードは次のとおりです。

int return_Max_volumn(List VolumnList)
{
    maxVolumn = 0;
    minimaxLeft = Integer.Max_value;
    for (Volumn v: VolumnList)
         for i = 1 to K people
             targeVolumn = v/i;
             NumberofpeoplecanGetcake = v1/targetVolumn + 
                 v2/targetVolumn + ... + vn/targetVolumn
             if (numberofPeopleCanGetcake >= k)
                  remainVolumn = (v1 mod targetVolumn) + (v2 mod targetVolumn)
                   + (v3 mod targetVolumn + ... + (vn mod targetVolumn)
                  if (remainVolumn < minimaxLeft)
                       update maxVolumn to be targetVolumn;
                       update minimaxLeft to be remainVolumn


     return maxVolumn
}

score 1 · Accepted Answer

私が検討するアプローチは次のとおりです。

すべてのケーキがサイズの小さい順に並べ替えられていると仮定しましょう。つまり、ケーキがVn最大で、ケーキV1が最小です。

すべての人の間で最大のケーキのみを分割することにより、最初の中間解を生成します。kすなわちV = Vn / k。
よりも小さいすべてのケーキをすぐに破棄Vします。これらのケーキを含む中間ソリューションは、ステップ 1 の中間ソリューションよりも悪いVb, ..., Vnことが保証されています。ここで、b1 以上のケーキが残ります。
一番大きなものを除いてすべてのケーキが捨てられたら、それで終わりです。Vが解決策です。終わり。
複数のケーキが残っているので、いくつかのスライスを 2 番目に大きいケーキに再分配することによって、中間解を改善しましょう。つまり、 so thatVn-1の最大値を見つけます。これは、の現在の値と上限の間でバイナリ検索を実行するか、より巧妙な方法で行うことができます。Vfloor(Vn / V) + floor(Vn-1 / V) = kV(Vn + Vn-1) / k
繰り返しますが、ステップ 2 で行ったように、より小さいすべてのケーキをすぐに破棄します。これらのケーキを含む中間ソリューションは、ステップ 4 の中間ソリューションよりも悪いVことが保証されています。
2 つの大きなケーキを除いて、すべてのケーキが破棄された場合は、完了です。Vが解決策です。終わり。
新しい「大きな」ケーキを右から左の方向に巻き込み続け、中間の解決策を改善し、「小さな」ケーキを左から右の方向に廃棄し続け、残りのケーキがすべて使い果たされるまで続けます。

PS ステップ 4 の複雑さは、問題全体の複雑さと同等のようです。つまり、上記は最適化アプローチと見なすことができますが、実際の解決策ではありません。まあ、それだけの価値はあります... :)

score -2 · Accepted Answer

だからここに私がそれがうまくいくと思ったアルゴリズムがあります：

ボリュームを最大から最小に並べ替えます。
最大のケーキを 1...k 人に分割します。つまり、ターゲット = ボリューム[0]/i、ここで i = 1,2,3,4,...,k
ターゲットが k より大きいピースの合計数になる場合は、数 i を減らして再試行します。
ケーキの総数が K 以上になるが(i-1)になるとケーキの総数が k 未満になる最初の数iを見つけます。このボリュームを baseVolume として記録します。
残りのケーキごとに、人数で割った残りのボリュームの最小の割合を見つけます。
この量を baseVolume(baseVolume += division) に追加し、すべてのボリュームが分割できる総ピースを再計算します。新しいボリュームのピースが少ない場合は、以前の値を返します。それ以外の場合は、手順 6 を繰り返します。

Javaコードは次のとおりです。

public static int getKonLagestCake(Integer[] sortedVolumesList, int k) {
    int result = 0;
    for (int i = k; i >= 1; i--) {
        double volumeDividedByLargestCake = (double) sortedVolumesList[0]
                / i;
        int totalNumber = totalNumberofCakeWithGivenVolumn(
                sortedVolumesList, volumeDividedByLargestCake);
        if (totalNumber < k) {
                result = i + 1;
                break;
        }
    }
    return result;
}


public static int totalNumberofCakeWithGivenVolumn(
        Integer[] sortedVolumnsList, double givenVolumn) {
    int totalNumber = 0;
    for (int volume : sortedVolumnsList) {
        totalNumber += (int) (volume / givenVolumn);
    }
    return totalNumber;
}

public static double getMaxVolume(int[] volumesList, int k) {
    List<Integer> list = new ArrayList<Integer>();
    for (int i : volumesList) {
        list.add(i);
    }

    Collections.sort(list, Collections.reverseOrder());
    Integer[] sortedVolumesList = new Integer[list.size()];
    list.toArray(sortedVolumesList);

    int previousValidK = getKonLagestCake(sortedVolumesList, k);
    double baseVolume = (double) sortedVolumesList[0] / (double) previousValidK;

    int totalNumberofCakeAvailable = totalNumberofCakeWithGivenVolumn(sortedVolumesList, baseVolume);

    if (totalNumberofCakeAvailable == k) {
        return baseVolume;
    } else {
        do
        {
            double minimumAmountAdded = minimumAmountAdded(sortedVolumesList, baseVolume);

            if(minimumAmountAdded == 0)
            {
                return baseVolume;
            }else
            {
                baseVolume += minimumAmountAdded;
                int newTotalNumber = totalNumberofCakeWithGivenVolumn(sortedVolumesList, baseVolume);

                if(newTotalNumber == k)
                {
                    return baseVolume;
                }else if (newTotalNumber < k)
                {
                    return (baseVolume - minimumAmountAdded);
                }else
                {
                    continue;
                }
            }

        }while(true);
    }

}

public static double minimumAmountAdded(Integer[] sortedVolumesList, double volume)
{
    double mimumAdded = Double.MAX_VALUE;
    for(Integer i:sortedVolumesList)
    {
        int assignedPeople = (int)(i/volume);
        if (assignedPeople == 0)
        {
            continue;
        }
        double leftPiece = (double)i - assignedPeople*volume;

        if(leftPiece == 0)
        {
            continue;
        }

        double division = leftPiece / (double)assignedPeople;
        if (division < mimumAdded)
        {
            mimumAdded = division;
        }
    }

    if (mimumAdded == Double.MAX_VALUE)
    {
        return 0;
    }else
    {
        return mimumAdded;
    }
}

コメントをお待ちしております。ありがとう

algorithm - N個のケーキをM人に分けて無駄を最小限にする

4 に答える 4

Related

Reference