在 Python 中找到以优化方式填充水果所需的最低成本的程序

假设我们有一个名为fruits 的列表和另外两个值k 和cap。其中每个fruits[i]有3个值：[c, s, t]，这表示每个水果i的成本为c，每个水果的大小为s，总共有t个。k代表容量上限的果篮数量。我们希望按照以下顺序填充水果篮 -

• 每个篮子只能装相同类型的水果

• 每个篮子都应尽可能装满

• 每个篮子都应该尽可能便宜

因此，我们必须找到填充尽可能多的篮子所需的最低成本。

所以，如果输入像 Fruits = [[5, 2, 3],[6, 3, 2],[2, 3, 2]] k = 2 cap = 4，那么输出将是 12，因为我们可以取两个水果 0，因为有了这两个，我们可以使第一个篮子装满总大小 2+2=4，花费 5+5=10。然后，我们使用水果 2 中的一种，因为它更便宜。这需要 2 个单位。

示例

让我们看看以下实现以获得更好的理解 -

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

         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