Python程序：以优化方式填充水果并找到最小成本

假设我们有一个名为 fruits 的列表以及另外两个值 k 和 cap。其中每个 fruits[i] 都有三个值：[c, s, t]，这表示水果 i 的每个水果成本为 c，每个水果的大小为 s，并且共有 t 个。k 表示容量为 cap 的水果篮的数量。我们希望在以下约束条件下填充水果篮，并按照以下顺序进行：-

  • 每个篮子只能装同一类型的水果
  • 每个篮子应该尽可能装满
  • 每个篮子应该尽可能便宜

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

因此，如果输入类似于 fruits = [[5, 2, 3],[6, 3, 2],[2, 3, 2]] k = 2 cap = 4，则输出将为 12，因为我们可以取两个水果 0，因为用这两个水果，我们可以使第一个篮子装满，总大小为 2+2=4，成本为 5+5=10。然后，我们使用一个水果 2，因为它更便宜。这花费了 2 个单位。

为了解决这个问题，我们将遵循以下步骤：-

  • options := 一个新列表
  • 对于 fruits 中的每个三元组 (c, s, t)，执行以下操作：
    • 当 t > 0 时，执行以下操作：
      • fnum := (cap / s) 的向下取整和 t 的最小值
      • 如果 fnum 等于 0，则
        • 退出循环
      • bnum := t / fnum 的向下取整
      • 在 options 的末尾插入三元组 (cap - fnum * s, fnum * c, bnum)
      • t := t - bnum * fnum
  • ans := 0
  • 对于排序后的 options 列表中的每个三元组 (left_cap, bcost, bnum)，执行以下操作：
    • bfill := k 和 bnum 的最小值
    • ans := ans + bcost * bfill
    • k := k - bfill
    • 如果 k 等于 0，则
      • 退出循环
  • 返回 ans

示例

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

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

更新于： 2021年10月18日

1K+ 浏览量

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告