পাইথনে ঘর আঁকার জন্য ন্যূনতম খরচ খুঁজে বের করার প্রোগ্রাম

ধরুন m আকারের একটি অ্যারে রয়েছে, একটি ছোট শহরে m ঘরগুলিকে প্রতিনিধিত্ব করে, প্রতিটি বাড়িকে অবশ্যই n রঙের একটি দিয়ে আঁকা উচিত (রঙগুলিকে 1 থেকে n পর্যন্ত লেবেল করা হয়েছে), এবং কিছু বাড়ি ইতিমধ্যেই আঁকা হয়েছে, তাই এর প্রয়োজন নেই আবার আঁকা। যে সব বাড়ি একই রঙে রঙ করা হয় তাকে পাড়া বলে। আমাদের অ্যারে হাউস রয়েছে, যেখানে ঘরগুলি বাড়ির রঙের প্রতিনিধিত্ব করে, যদি রঙের মান 0 হয়, তবে এটি প্রতিনিধিত্ব করে যে বাড়িটি এখনও রঙিন হয়নি। আমাদের খরচ নামে আরেকটি অ্যারে আছে, এটি একটি 2D অ্যারে যেখানে খরচ[i, j] রঙ j+1 সহ রঙিন ঘর i-এর খরচকে প্রতিনিধিত্ব করে। আমাদের আরেকটি ইনপুট মান আছে যার নাম টার্গেট। বাকি সব ঘর এমনভাবে পেইন্ট করার জন্য আমাদের ন্যূনতম খরচ খুঁজে বের করতে হবে যাতে আশেপাশের নির্দিষ্ট সংখ্যা ঠিক থাকে। যদি আমরা একটি সমাধান না পেতে পারি তাহলে -1 ফিরে আসুন।

সুতরাং, যদি ইনপুট ঘরের মত হয় =[0,2,1,2,0] খরচ =[[1,10],[10,1],[10,1],[1,10],[5, 1]] n =2 টার্গেট =3, তাহলে আউটপুট 11 হবে কারণ কিছু বাড়ি ইতিমধ্যেই আঁকা হয়েছে, তাই আমাদের ঘরগুলিকে এমনভাবে রঙ করতে হবে যেমন [2,2,1,2,2], তিনটি আছে প্রতিবেশী, [{2,2}, {1}, {2,2}]। এবং প্রথম এবং শেষ বাড়ি আঁকার মোট খরচ (10 + 1) =11।

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

• m :=বাড়ির আকার

• একটি ফাংশন হেল্পার() সংজ্ঞায়িত করুন। এর জন্য i, p_col, grp

  লাগবে

• যদি আমি m এর মত হয়, তাহলে

  • 0 রিটার্ন করুন যদি grp টার্গেটের মত হয় অন্যথায় inf

• যদি ঘরগুলি[i] 0 এর মতো না হয়, তাহলে

  • রিটার্ন হেল্পার(i + 1, houses[i], grp + (1 যদি p_col ঘরের মত না হয়[i], অন্যথায় 0)

• মোট :=inf

• 1 থেকে n রেঞ্জের কলের জন্য, করুন

  • মোট =সর্বনিম্ন মোট এবং (খরচ[i, col - 1] + সাহায্যকারী(i + 1, col, grp + (1 যখন p_col col এর মত হয় না অন্যথায় 0)))

• মোট রিটার্ন

• মূল পদ্ধতি থেকে নিম্নলিখিতগুলি করুন

• উত্তর :=সাহায্যকারী(0, -1, 0)

• উত্তর দিন যদি উত্তর না হয় তাহলে inf অন্যথায় -1

উদাহরণ

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

def solve(houses, cost, n, target):m =len(houses) def helper(i, p_col, grp):if i ==m:রিটার্ন 0 if grp ==target else float('inf') ) if houses[i] !=0:রিটার্ন হেল্পার(i + 1, houses[i], grp + int(p_col !=houses[i])) total =float('inf') পরিসরে কলের জন্য (1, n + 1):মোট =মিনিট(মোট, খরচ[i][কল - 1] + সাহায্যকারী(i + 1, col, grp + int(p_col !=col))) মোট উত্তর =সাহায্যকারী(0, -1) , 0) উত্তর দিন যদি ans !=float('inf') অন্য -1 ঘর =[0,2,1,2,0] খরচ =[[1,10],[10,1],[10,1] ,[1,10],[5,1]]n =2টার্গেট =3প্রিন্ট(সল্ভ(বাড়ি, খরচ, n, টার্গেট))

ইনপুট

আউটপুট

11