ظرفیت حمل بسته در ظرف D روز راه حل کد


سطح دشواری متوسط
اغلب در آمازون
صف جستجوی دودویی

بیان مسأله

در مسئله "ظرفیت حمل بسته ها طی D روز" ، بسته هایی در بندر A داریم که باید در روزهای D به بندر B منتقل شوند.

به ما یک آرایه وزنه ای داده می شود که حاوی وزن هر بسته و تعداد روزهایی است که باید بسته ها را انتقال دهیم. وظیفه ما یافتن حداقل ظرفیت بار کشتی است که برای انتقال بسته ها از بندر A به بندر B در روز D استفاده می شود.

راه حل کد برای ظرفیت حمل بسته در ظرف D روز

مثال

weights = [1,2,3,4,5,6,7,8,9,10], D = 5
15

شرح: کشتی بسته ها را به روش زیر منتقل می کند:

روز اول: 1,2,3,4,5،XNUMX،XNUMX،XNUMX،XNUMX

روز دوم 2: 6,7،XNUMX

روز سوم 3: 8

روز چهارم 4: 9

روز پنجم 5: 10

به این ترتیب حداقل ظرفیت بار کشتی باید 15 باشد تا کلیه بسته ها در 5 روز منتقل شود.

رویکرد ظرفیت حمل بسته ها در ظرف D روز راه حل کد

اولین و مهمترین مسئله برای حل این مشکل ارائه مشاهدات است. در اینجا چند مشاهده برای فاصله جستجوی ما وجود دارد:

  1. ظرفیت بار کشتی حداقل باید برابر با بسته حداکثر وزن حداکثر (وزنه ها) باشد. بیایید آن را به عنوان آغاز.
  2. ما می توانیم حداکثر ظرفیت کشتی را به مجموع وزن تمام بسته هایی که جمع (وزن) هستند محدود کنیم. بیایید آن را به عنوان پایان.

اکنون فاصله جستجوی خود را داریم. فرض کنید اندازه این فاصله باشد طول و تعداد بسته ها می باشد n.  رویکرد ساده لوحانه می تواند بررسی هر مقدار در فاصله زمانی باشد که آیا این ظرفیت بار می تواند بسته ها را با موفقیت در روز D انتقال دهد و حداقل را از آنها انتخاب کند. پیچیدگی زمانی برای رویکرد ساده لوحانه طول * n خواهد بود.

ما می توانیم پیچیدگی زمان را با استفاده از جستجوی دودویی به جای جستجوی خطی بهبود بخشیم.

پیچیدگی زمان با استفاده از جستجوی دودویی رویکرد log خواهد شد (طول) * n.

پیاده سازی

کد C ++ برای ظرفیت حمل بسته ها در D D Leetcode Solution

#include <bits/stdc++.h>
using namespace std; 
    int shipWithinDays(vector<int>& weights, int D) {
        int left = 0, right = 0;
        for (int w: weights) {
            left = max(left, w);
            right += w;
        }
        while (left < right) {
            int mid = (left + right) / 2, requirement = 1, tillnow = 0;
            for (int w: weights) {
                if (tillnow + w > mid) {
                   requirement += 1;
                   tillnow = 0;
                }
                tillnow += w;
            }
            if (requirement > D) left = mid + 1;
            else right = mid;
        }
        return left;
    }
int main() 
{ 
 vector<int> arr = {1,2,3,4,5,6,7,8,9,10}; 
 int d=5;                               

 cout<<shipWithinDays(arr,d)<<endl;
 return 0;
}
15

کد جاوا برای حمل و نقل بسته های ظرف مدت D Day Leetcode Solution

public class Tutorialcup {
    public static int shipWithinDays(int[] weights, int D) {
        int left = 0, right = 0;
        for (int w: weights) {
            left = Math.max(left, w);
            right += w;
        }
        while (left < right) {
            int mid = (left + right) / 2, requirement = 1, tillnow = 0;
            for (int w: weights) {
                if (tillnow + w > mid) {
                   requirement += 1;
                   tillnow = 0;
                }
                tillnow += w;
            }
            if (requirement > D) left = mid + 1;
            else right = mid;
        }
        return left;
    }
  public static void main(String[] args) {
    int [] arr = {1,2,3,4,5,6,7,8,9,10}; 
     int d=5; 
    int ans= shipWithinDays(arr,d);
    System.out.println(ans);
  }
}
15

تجزیه و تحلیل پیچیدگی ظرفیت حمل بسته در ظرف D روز راه حل کد

پیچیدگی زمانی

پیچیدگی زمانی کد فوق است O (n * log (طول)) زیرا ما در حال بارگیری در آرایه وزن (طول) بار هستیم. در اینجا n و Length به ترتیب تعداد بسته ها و اندازه فاصله جستجو هستند.

پیچیدگی فضا

پیچیدگی فضایی کد فوق است O (1) زیرا ما فقط از یک متغیر برای ذخیره پاسخ استفاده می کنیم.

منابع