পাইথনে k বিভিন্ন রং দিয়ে বেড়া আঁকার ন্যূনতম খরচ খুঁজে বের করার প্রোগ্রাম

ধরুন আমরা K বিভিন্ন রং দিয়ে N বেড়ার সারি আঁকতে চাই। কোন দুটি প্রতিবেশী বেড়া একই রঙের নয় তা নিশ্চিত করার সময় আমরা খরচ কমাতে চাই। তাই যদি আমাদের একটি N x K ম্যাট্রিক্স থাকে যেখানে nth সারি এবং kth কলাম kth রঙ দিয়ে nম বেড়া আঁকার খরচকে প্রতিনিধিত্ব করে, তাহলে আমাদের সর্বনিম্ন খরচ খুঁজে বের করতে হবে যা এই লক্ষ্য অর্জন করে।

সুতরাং, যদি ইনপুট মত হয়

তাহলে আউটপুট 14 হবে, কারণ আমরা নিম্নলিখিত রঙের সূচকগুলি নির্বাচন করতে পারি (প্রথম বেড়া থেকে শুরু করে) − 5 → 2 → 3 → 4৷

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

• n :=ম্যাট্রিক্সের সারি গণনা

• fc :=0, ft :=0

• sc :=1, st :=0

• ম্যাট্রিক্সের প্রতিটি সারির জন্য, করুন

  • nfc :=-1, nft :=inf

  • nsc :=-1, nst :=inf

  • প্রতিটি সূচক i এবং মান t সারির জন্য, করুন

    • ct :=t +(ft যদি আমি fc এর মত না হয় অন্যথায় st)

    • যদি ct <=nft, তাহলে

      • nsc :=nfc, nst :=nft

      • nfc :=i, nft :=ct

    • অন্যথায় যখন ct <=nst, তারপর

      • nsc :=i, nst :=ct

  • fc :=nfc, ft :=nft

  • sc :=nsc, st :=nst

• ফিরুন ft

উদাহরণ

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

শ্রেণির সমাধান:def solve(self, matrix):n =len(matrix) fc, ft =0, 0 sc, st =1, 0 inf =int(1e18) ম্যাট্রিক্সে সারির জন্য:nfc, nft =- 1, inf nsc, nst =-1, inf এর জন্য i, t enumerate(সারিতে):ct =t + (ft যদি i !=fc else st) যদি ct <=nft:nsc, nst =nfc, nft nfc, nft =i, ct elif ct <=nst:nsc, nst =i, ct fc, ft =nfc, nft sc, st =nsc, nst রিটার্ন ftob =Solution()matrix =[ [6, 4, 5], [ 3, 2, 7], [3, 4, 5], [5, 4, 4]]print(ob.solve(matrix))

ইনপুট

আউটপুট

14