পাইথনে প্রদত্ত দুটি তালিকার যে কোনো একটির চূড়ান্ত সূচকে পৌঁছানোর জন্য খরচ খোঁজার প্রোগ্রাম

ধরুন আমাদের কাছে একই দৈর্ঘ্যের nums0 এবং nums1 সংখ্যার দুটি তালিকা এবং দূরত্ব হিসাবে d এবং খরচ হিসাবে c অন্য দুটি মান রয়েছে। যদি আমরা সূচক 0 থেকে nums0 বা nums1 থেকে শুরু করি এবং যেকোন একটি তালিকার চূড়ান্ত সূচকে শেষ করতে চাই। এখন, প্রতিটি রাউন্ডে, আমরা খরচের খরচের জন্য অন্য তালিকায় স্যুইচ করতে নির্বাচন করতে পারি। তারপরে আমরা সর্বাধিক d দূরত্বে এগিয়ে যেতে পারি যেখানে একটি সূচকে অবতরণের c খরচ সেই বিন্দুর মান। তাই আমাদের কাজটি সম্পূর্ণ করার জন্য সম্ভাব্য সর্বনিম্ন মোট খরচ খুঁজে বের করতে হবে।

সুতরাং, ইনপুট যদি nums0 =[2, 3, 10, 10, 6] nums1 =[10, 10, 4, 5, 100] d =2 c =3 এর মত হয়, তাহলে আউটপুট হবে 18, যেমন আমরা পারি। 2 থেকে শুরু করুন, তারপরে দ্বিতীয় তালিকা থেকে 4-এ স্যুইচ করুন, আবার প্রথম তালিকা থেকে 6-এ ফিরে যান। তাই খরচ 2 + 4 + 6 =12 এবং প্রতিটি খরচ 3 সহ দুবার স্যুইচ করুন তাই মোট 18।

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

• সুইচ করুন :=nums0 এর জন্য 0 কী এবং nums1 এর জন্য কী 1 সহ একটি মানচিত্র
• একটি ফাংশন অনুসন্ধান () সংজ্ঞায়িত করুন। এর জন্য idx, nums
লাগবে
• যদি idx>=সুইচের আকার [সংখ্যা] , তারপর
  • রিটার্ন ইনফ
• যদি idx সুইচের আকার [সংখ্যা] - 1 এর মতো হয়, তাহলে
  • রিটার্ন সুইচ[সংখ্যা, -1]
• c :=inf
• আমি 1 থেকে dist + 1 রেঞ্জের জন্য,
  করুন
  • c :=ন্যূনতম c এবং সুইচ [nums, idx] + search(idx + i, nums)
  • c :=ন্যূনতম c এবং স্যুইচ [nums, idx] + খরচ + অনুসন্ধান(idx + i, সংখ্যার উল্টো)
• রিটার্ন c
• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -
• সর্বনিম্ন অনুসন্ধান (0, 0) এবং অনুসন্ধান (0, 1) ফেরত দিন

উদাহরণ (পাইথন)

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

শ্রেণীর সমাধান:def solve(self, nums0, nums1, dist, cost):switch ={0:nums0, 1:nums1} def search(idx, nums):if idx>=len(switch[nums]) :রিটার্ন ফ্লোট("inf") if idx ==len(switch[nums]) - 1:রিটার্ন সুইচ[nums][-1] c =float("inf") in range(1, dist + 1) এর জন্য :c =min(c, switch[nums][idx] + search(idx + i, nums)) c =min(c, switch[nums][idx] + খরচ + অনুসন্ধান(idx + i, int(সংখ্যা নয় ))) ফিরুন , 100]d =2c =3print(ob.solve(nums0, nums1, d, c))

ইনপুট

আউটপুট

18