পাইথনে D দিনের মধ্যে প্যাকেজ শিপ করার ন্যূনতম ক্যাপাসিটি

মনে করুন একটি কনভেয়র বেল্টে প্যাকেজ রয়েছে যেগুলো D দিনের মধ্যে এক পোর্ট থেকে অন্য পোর্টে শিপ করতে হবে। i-তম প্যাকেজের ওজন weights[i]। প্রতিদিন আমরা শিপে প্যাকেজ লোড করব। শিপের ম্যাক্সিমাম ওজন ক্যাপাসিটি এর চেয়ে বেশি লোড করা যাবে না। আমাদের শিপের ন্যূনতম ওজন ক্যাপাসিটি বের করতে হবে যাতে D দিনের মধ্যে সকল প্যাকেজ শিপ করা যায়।

ইনপুট [3,2,2,4,1,4] এবং D = 3 হলে আউটপুট 6, কারণ ক্যাপাসিটি ৬ হলো ন্যূনতম যা ৩ দিনে শিপ করতে পারবে:

• দিন ১: 3, 2

• দিন ২: 2, 4

• দিন ৩: 1, 4

এটি সমাধান করতে আমরা নিচের ধাপগুলো ফলো করব (বাইনারি সার্চ + গ্রিডি চেক):

• solve(weights, maxWeight, ships) রিকার্সিভ ফাংশন ডিফাইন করুন:

  • index := 0

  • for i in range(len(ships)):

    • ships[i] := 0

    • while index < len(weights) and ships[i] + weights[index] <= maxWeight:

      • ships[i] += weights[index], index++

  • return index == len(weights)

• মেইন মেথড:

  • ships := size D অ্যারে, ০ দিয়ে পূরণ

  • max_w := max(weights)

  • low := max_w, high := max_w * len(weights) + 1

  • while low < high:

    • mid := low + (high - low) // 2

    • যদি solve(weights, mid, ships) true, তবে high := mid, অন্যথায় low := mid + 1

  • return high

উদাহরণ

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