পাইথনে ডি দিনের মধ্যে প্যাকেজ পাঠানোর ক্ষমতা

ধরুন একটি কনভেয়র বেল্টে প্যাকেজ রয়েছে যেগুলি D দিনের মধ্যে এক বন্দর থেকে অন্য বন্দরে পাঠানো হবে। এখানে কনভেয়র বেল্টের i-th প্যাকেজের ওজন রয়েছে [i]। প্রতিদিন, আমরা বেল্টে প্যাকেজ সহ জাহাজটি লোড করব। আমরা জাহাজের সর্বোচ্চ ওজন ক্ষমতার চেয়ে বেশি ওজন লোড করব না। আমাদের জাহাজের সর্বনিম্ন ওজনের ক্ষমতা খুঁজে বের করতে হবে যার ফলে কনভেয়র বেল্টের সমস্ত প্যাকেজ D দিনের মধ্যে পাঠানো হবে। সুতরাং যদি ইনপুটটি [3,2,2,4,1,4] এবং D =3 এর মত হয়, তাহলে আউটপুট হবে 6, কারণ জাহাজের ধারণক্ষমতা 6 হলেই 3 দিনে সমস্ত প্যাকেজ পাঠানোর সর্বনিম্ন, যেমন −

• দিন 1:3, 2

• দিন 2:2, 4

• দিন 3:1, 4

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি পুনরাবৃত্ত ফাংশন সমাধান () সংজ্ঞায়িত করুন। এটি ওয়েট অ্যারে, ম্যাক্সওয়েট এবং শিপ অ্যারে নেবে, এটি এরকম কাজ করবে −

• সূচক :=0

• আমি 0 থেকে জাহাজ অ্যারের দৈর্ঘ্যের মধ্যে

  • জাহাজ[i] :=0

  • যখন সূচক <ওজন এবং জাহাজের দৈর্ঘ্য[i] + ওজন[সূচক] <=সর্বোচ্চ ওজন

    • জাহাজ[i] :=জাহাজ[i] + ওজন[সূচক]

    • সূচক 1 দ্বারা বৃদ্ধি করুন

• সত্য ফেরত দিন, যখন সূচক =ওজনের দৈর্ঘ্য, অন্যথায় মিথ্যা

• প্রধান পদ্ধতির মত কাজ করবে

• ships :=D এর মতো আকারের একটি অ্যারে, এবং 0

  দিয়ে এটি পূরণ করুন

• সর্বোচ্চ ওজন :=সর্বোচ্চ ওজন

• কম :=সর্বোচ্চ ওজন, উচ্চ :=সর্বোচ্চ ওজন + ওজন অ্যারের দৈর্ঘ্য + 1

• যখন কম <উচ্চ

  • মধ্য :=নিম্ন + (উচ্চ - নিম্ন)/2

  • যদি সমাধান (ওজন, মধ্য, জাহাজ) সত্য হয়, তাহলে উচ্চ :=মধ্য, অন্যথায় নিম্ন :=মধ্য + 1

• উচ্চ রিটার্ন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

class Solution(object):
   def shipWithinDays(self, weights, D):
      ships = [0 for i in range(D)]
      max_w = max(weights)
      low = max_w
      high = max_w * len(weights)+1
      while low<high:
         mid = low + (high-low)//2
         if self.solve(weights,mid,ships):
            high = mid
         else:
            low = mid+1
      return high
   def solve(self,weights,max_w,ships):
      index = 0
      for i in range(len(ships)):
         ships[i] = 0
         while index < len(weights) and ships[i]+weights[index]<= max_w:
            ships[i] += weights[index]
            index+=1
      return index == len(weights)
ob = Solution()
print(ob.shipWithinDays([3,2,2,4,1,4],3))

ইনপুট

[3,2,2,4,1,4]
3

আউটপুট

6