Computer >> Máy Tính >  >> Lập trình >> Python

Chương trình tìm chi phí tối thiểu cần thiết để lấp đầy trái cây theo cách được tối ưu hóa bằng Python

Giả sử chúng ta có một danh sách được gọi là trái cây và hai giá trị khác là k và cap. Trong đó mỗi trái cây [i] có ba giá trị:[c, s, t], điều này cho biết trái cây tôi có giá c mỗi trái, kích thước của mỗi trái là s và có tổng t của chúng. K thể hiện số giỏ trái cây có giới hạn dung tích. Chúng tôi muốn lấp đầy giỏ trái cây với các ràng buộc sau theo thứ tự này -

  • Mỗi giỏ chỉ có thể đựng các loại trái cây giống nhau
  • Mỗi giỏ phải càng đầy càng tốt
  • Mỗi giỏ phải càng rẻ càng tốt

Vì vậy, chúng tôi phải tìm chi phí tối thiểu cần thiết để lấp đầy nhiều giỏ nhất có thể.

Vì vậy, nếu đầu vào giống như các quả =[[5, 2, 3], [6, 3, 2], [2, 3, 2]] k =2 cap =4, thì đầu ra sẽ là 12, bởi vì chúng ta Có thể lấy hai quả 0 vì với hai quả này, ta có thể làm đầy giỏ thứ nhất với tổng kích thước 2 + 2 =4, giá thành là 5 + 5 =10. Sau đó, chúng tôi sử dụng một trong 2 trái cây vì nó rẻ hơn. Chi phí này là 2 đơn vị.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

  • options:=một danh sách mới
  • đối với mỗi bộ ba (c, s, t) trong quả, thực hiện
    • while t> 0, do
      • fnum:=tối thiểu của tầng (giới hạn / s) và t
      • nếu fnum giống 0, thì
        • ra khỏi vòng lặp
      • bnum:=tầng của t / fnum
      • chèn bộ ba (cap - fnum * s, fnum * c, bnum) vào cuối các tùy chọn
      • t:=t - bnum * fnum
  • ans:=0
  • đối với mỗi bộ ba (left_cap, bcost, bnum) trong danh sách tùy chọn đã sắp xếp, hãy thực hiện
    • bfill:=tối thiểu là k và bnum
    • ans:=ans + bcost * bfill
    • k:=k - bfill
    • nếu k giống 0, thì
      • ra khỏi vòng lặp
  • trả lại ans

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn - 

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))

Đầu vào 

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

Đầu ra 

12