用 Python 编写程序，以优化方式查找装满水果所需的最小成本

pythonserver side programmingprogramming更新于 2026/1/20 2:52:17

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

每个篮子只能容纳相同类型的水果
每个篮子应尽可能装满
每个篮子应尽可能便宜

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

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

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

options := a new list
对于水果中的每个三元组 (c, s, t)，执行
- while t > 0，执行
  - 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 相同，则
  - 退出循环
返回 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))