4

私は100個のジャガイモが入った袋を持っています。じゃがいもを N 個のバケットに分割する必要があります。各バケツには、15 ～ 60 個のジャガイモが必要です。

明らかに、これをコードにするには、段階的な解決策が必要です。

私がこれまでに持っている最良の方法：

バケットの最小数: 100/60 = 1 (40) => 切り上げ => 2
バケットの最大数: 100/15 = 6 (10) => 切り捨て => 6

したがって、最小で 2 個、最大で 6 個のバケットを持つことができます。ここで、乱数を選択します (すべてのソリューションではなく、1 つのソリューションのみが必要なため)。

3 つ選びましょう。
バケツあたりのジャガイモ: 100/3 = 33 (1)
バケツ: 33、33、34。

ここがトリッキーな部分です。これは元の問題の解決策ですが、数字をそれよりもランダムにする必要があるため、私にはうまくいきません。問題の状態は 15 ～ 60 でしたが、ここでは 33 ～ 34 しか得られません。

ここからの解決策の 1 つは、各バケットから数値の加算と減算を開始することです。おそらくこれを10回ほど繰り返しますが、もっと良い方法があるに違いないと思います。

何か案は？

4

5 に答える 5

2

まず、必要最小限の数を配布します。あなたの例では、各バケットに 15 を入れます。バケツが 3 つある場合は、45 を 3 つに均等に入れます。残り (R): 55。各バケット (C1、C2、C3) の残り容量: 45。

数 k を選びます (k の選び方については脚注を参照してください)。R より大きい場合は、R (k=min(k,R) ) に設定します。バケツ i をランダムに選びます。Ci がより小さい場合、k は k を Ci に設定します ( k=min(k,Ci) )。次に、k 個のジャガイモをバケツ i に入れます。R と Ci を更新します (R=Rk、Ci=Ci-k)。すべてのジャガイモが完成するまでこれを繰り返します (R=0)。

脚注: ピッキング k

k=1 を設定するか、任意の適切な分布から k を選択できます (例: k を 1 から 10 までランダムに選択します)。

コード

import random
def distPotato(R, N, minP, maxP):
    C = [maxP-minP for i in range(N)]
    V = [minP for i in range(N)]
    R-=sum(V)    
    while(R>0):
        k = random.choice(range(10)) + 1
        i = random.choice(range(N))
        k = min(k,R)
        k = min(k, C[i])
        C[i]-=k
        R-=k
        V[i]+=k
    return V

distPotato(100,3,15,60)
于 2012-05-12T07:29:58.403 に答える
0

肉屋にある長さの牛肉を想像すると、肉屋はできるだけ短い時間でそのランダムなサイズの N ピースにカットするように求められます。

彼の最初の行動は、肉を無作為に叩き落とすことであり、N-1カットを行うまで、前のスライスや端に近づきすぎないように注意します.

あなたの目的のために、牛肉のスラブは代わりにジャガイモの列である可能性があります.

したがって、これを疑似コードに変換するには:

initiate a list of chosen potatoes to empty
while you have chosen less than N-1 potatos
    pick a potato
    if the potato is less than 15 potatoes away from a side
        continue
    if the potato is less than 15 potatoes away from a chosen potato
        continue
    add this potato to the chosen list
sort the chosen list
split the line of potatoes using the chosen potatoes as delimeters
于 2012-05-12T07:30:39.313 に答える
0

バケツに 15 個から 60 個のジャガイモをランダムに入れ、残りのジャガイモが 15 個未満になるようにすることをお勧めします。次に、最後にいっぱいにしたバケツを取り、残りのジャガイモをそのバケツに入れてみてください。60以下なら大丈夫！60 を超える場合は、バケツを半分に分割します。

これを数回行って、最終的に 74 個のジャガイモが得られたとします。バケツにジャガイモの乱数を入れます。60 個だとしましょう。14 個のジャガイモが残っています。次のバケツには少なすぎますが、最後のバケツに入れるには多すぎます。簡単に、前のバケツ（再び74個のジャガイモ）を注ぎ、それぞれ37個のバケツを2つ作ります。

問題は、最後の 2 つのバケツが他のバケツのようにランダムにならない (または、少なくとも「ランダム」ではない) ことですが、バケツに 14 個未満のジャガイモを入れることはできないため、それについて行うことができます。

于 2012-05-12T07:42:53.890 に答える
0

まず、問題を少し単純化できることに注意してください。「各バケツには 15 ～ 60 個のジャガイモを入れる必要があり、バケツの合計は 100 にする必要があります」の代わりに、「これらの数字の合計が 100 になるように、0 ～ 45 (60 - 15) の間の n 個の数字が必要です。 n×15インチ。つまり、すべてのバケツに 15 個のジャガイモを入れて、残りのジャガイモを使用してバケツの残りのスペースを埋める方法を決定しようとしています。

n 個のバケツがあり、p 個のジャガイモが残っているとします。0 から 45 までの乱数 r を生成すると、p - r ポテトが残ります。残りの (n-1) 個のバケットを埋めることができますか?

  • (p - r) < 0 の場合、残りのバケットを埋めることができないのは明らかです。
  • (p - r) > 45 * (n - 1) の場合、これは実現不可能です。ジャガイモが多すぎて、バケツの容量を超えなければなりません。
  • それ以外の場合は、現在のバケツに r のジャガイモを入れても、次のバケツの解を見つけることができることがわかっています。

これを再帰的な解決策として書くことができます: 連続するバケットごとに、次のステップで解決策を見つけることが妨げられなくなるまで、ランダムな数のジャガイモを生成します。

以下は非常に粗雑な F# の実装であり、明らかに改良/最適化できますが、アルゴリズムの要点を示しています。allocation は、バケットにすでに割り当てられている数量を含む int のリストです。qty は割り当てられるジャガイモの残りの数量です。buckets は残りのバケットの数で、min、max はバケットの容量です。たとえば、ジャガイモ 100 個とバケツ 3 個の場合、ソルブ 100 3 15 60 を呼び出します。

結果として得られる割り当ては「可能な限りランダム」にする必要があります。つまり、可能な割り当てを同じ確率で生成する必要がありますが、1 つの注意点があります。バケットの順序は問題ではないと仮定しました。アルゴリズムがこれまでに割り当てられたものに基づいて残りのジャガイモを割り当てるとすれば、パスに応じて、リストの「先頭」が制限され、割り当てによって最初のバケットにより多くが割り当てられる可能性があります。「真の」ランダム割り当てが必要な場合は、割り当てが完了したらバケットをシャッフルする必要があります。

お役に立てれば！

let rng = new System.Random() 

let rec allocate allocation qty buckets min max =
      match buckets with
      | 0 -> allocation
      | 1 -> qty :: allocation
      | _ ->
         let candidate = rng.Next(min, max + 1) // try a number in [min,max]
         let rest = qty - candidate
         if rest < (buckets - 1) * min // not enough left
         then allocate allocation qty buckets min max // try again
         else if rest > (buckets - 1) * max // too much left
         then allocate allocation qty buckets min max // try again
         else allocate (candidate :: allocation) rest (buckets - 1) min max

let solve qty buckets min max =
   if min * buckets > qty then failwith "unfeasible"
   if max * buckets < qty then failwith "unfeasible"
   allocate [] qty buckets min max
于 2012-05-12T19:01:36.313 に答える