Pythonで繰り返し整数を配布するプログラム

配列numがあるとすると、最大50個の一意の値があります。また、quantityという別の配列があります。ここで、quantity [i]は、i番目の顧客が注文した値の量を示します。次のような数値を配布できるかどうかを確認する必要があります

• i番目の顧客は正確に数量[i]のアイテムを受け取ります

• i番目の顧客が得る価値はすべて等しく、

• すべてのお客様が満足しています。

したがって、入力がnums =[5,1,2,2,3,4,4,3,3] amount =[2,2,3]のようである場合、2人の顧客が2つの要素を必要としているため、出力はTrueになります。それぞれ、[2,2]と[4,4]を取得でき、3番目のアイテムは3つのアイテムが必要なので、[3,3,3]を取得できるので、すべて満足しています。

これを解決するには、次の手順に従います-

• 関数util（）を定義します。これにはi、cntrが必要です

• iが数量のサイズと同じである場合、

  • Trueを返す

• temp_counter：=cntrのコピーを作成する

• cntrの各cntについて、実行します

  • cnt> =amount [i]の場合、

    • temp_counter [cnt]：=temp_counter [cnt]-1

    • temp_counter [cnt]が0と同じ場合、

      • temp_counterからcnt-th要素を削除します

    • rem：=cnt-数量[i]

    • temp_counter [rem]：=temp_counter [rem] + 1

    • util（i + 1、temp_counter）がtrueの場合、

      • Trueを返す

    • temp_counter [rem]：=temp_counter [rem]-1

    • temp_counter [rem]が0と同じ場合、

      • temp_counterからrem-th要素を削除します

  • temp_counter [cnt]：=temp_counter [cnt] + 1

• Falseを返す

• メインの方法から、次のようにします

• cnt：=numsに存在する数値のすべての頻度の頻度を保持するマップ

• 数量を逆の順序で並べ替える

• util（0、cnt）を返す

例

理解を深めるために、次の実装を見てみましょう

from collections import Counter
def solve(nums, quantity):
   def util(i, cntr):
      if i == len(quantity):
         return True

      temp_counter = cntr.copy()
      for cnt in cntr:
         if cnt >= quantity[i]:
            temp_counter[cnt] -= 1
            if temp_counter[cnt] == 0:
               temp_counter.pop(cnt)
         rem = cnt - quantity[i]
         temp_counter[rem] += 1

         if util(i+1, temp_counter):
            return True

         temp_counter[rem] -= 1
         if temp_counter[rem] == 0:
            temp_counter.pop(rem)
         temp_counter[cnt] += 1

      return False

   cnt = Counter(Counter(nums).values())
   quantity.sort(reverse=True)
   return util(0, cnt)

nums = [5,1,2,2,3,4,4,3,3]
quantity = [2,2,3]
print(solve(nums, quantity))

入力

[0,1,2,3,4], [[3,1],[1,3],[5,6]]

出力

True