Pythonで最適化された方法で果物を埋めるために必要な最小コストを見つけるためのプログラム

果物と呼ばれるリストと、別の2つの値kとcapがあるとします。各fruits[i]に3つの値[c、s、t]がある場合、これは、fruit iのコストがそれぞれcであり、それぞれのサイズがsであり、合計tがあることを示します。 kは、容量上限のフルーツバスケットの数を表します。フルーツバスケットに次の制約をこの順序で入力します-

• 各バスケットには同じ種類の果物しか入れられません
• 各バスケットはできるだけいっぱいにする必要があります
• 各バスケットはできるだけ安くする必要があります

したがって、できるだけ多くのバスケットを満たすために必要な最小コストを見つける必要があります。

したがって、入力がフルーツ=[[5、2、3]、[6、3、2]、[2、3、2]] k =2 cap =4の場合、出力は12になります。 2つのフルーツ0を取ることができます。これは、これら2つを使用すると、最初のバスケットを合計サイズ2 + 2 =4でいっぱいにすることができ、コストは5 + 5=10になるためです。次に、フルーツ2の方が安いので1つ使用します。これには2ユニットかかります。

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

• オプション：=新しいリスト
• 果物の各トリプレット（c、s、t）について、
  • t> 0の間、do
    • fnum：=（cap / s）とtの最小フロア
    • fnumが0と同じ場合、
      • ループから抜け出す
    • bnum：=t/fnumのフロア
    • オプションの最後にトリプレット（cap --fnum * s、fnum * c、bnum）を挿入します
    • t：=t --bnum * fnum
• ans：=0
• 並べ替えられたオプションのリストの各トリプレット（left_cap、bcost、bnum）について、
  を実行します。
  • bfill：=kとbnumの最小値
  • ans：=ans + bcost * bfill
  • k：=k --bfill
  • kが0と同じ場合、
    • ループから抜け出す
• 回答を返す

例

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

def solve(fruits, k, cap):
   options = []
   for c, s, t in fruits:
      while t > 0:
         fnum = min(cap // s, t)
         if fnum == 0:
            break
         bnum = t // fnum

         options.append((cap - fnum * s, fnum * c, bnum))
         t -= bnum * fnum
   ans = 0
   for left_cap, bcost, bnum in sorted(options):
      bfill = min(k, bnum)
      ans += bcost * bfill
      k -= bfill
      if k == 0:
         break

   return ans

fruits = [[5, 2, 3],[6, 3, 2],[2, 3, 2]]
k = 2
cap = 4
print(solve(fruits, k, cap))

入力

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

出力

12