কয়েন চেঞ্জ ডাইনামিক প্রোগ্রামিং আলগোরিদম

কোনো এক ঈদ এর ছুটি তে আবুল গেল আফ্রিকা তে ঘুরতে । এখন আফ্রিকা তে বাসে ভাড়া দেওয়ার সময় আবুল পরলো মোহা বিপদে। আফ্রিকা তে বাংলাদেশ এর মত ১, ২, ৫, ১০ বা ২০ টাকার নোটের বদলে আছে ২, ৩, ৬ এবং ৭ টাকার নোট। আবুল আবার অংকে মারাত্মক দুর্বল। ১৩ টাকা বাস ভাড়া কিভাবে যে দিবে তা সে ভেবে পাচ্ছে না।

এ তো মান সম্মান এর বেপার দেখা যায়। তো সে চুপি চুপি তার বন্ধু বাবুল কে বলল এইবারের মতো মান সম্মান বাচা দোস্ত। তো সেই বারের মতো বাবুল তার মান সম্মান বাচালো। কিন্তু বাবূল ভাবলো যে এইবার নাহয় ছিলাম আমি । কিন্তু আমি না থাকলে আবূলকে বাঁচাবে কে!! তো বাবূল ঠিক করলো সে আবুল কে একটা মোবাইল অ্যাপ বানিয়ে দিবে। যেটা দিয়ে নোট যতো টাকারি হোক না কেন টাকার অংক বসালেই বেরিয়ে আসবে যে কতো টাকার নোট কয়টা দরকার।

কিন্তু অ্যাপ বানাতে তো আগে চাই আলগোরিদম। তো চলুন দেখি বাবূল কে আলগোরিদম লিখতে সাহায্য করা যায় কিনা।। 

তো প্রথমে যতো যতো টাকা নোট আছে সেগুলোর একটা লিস্ট  বা অ্যারে বানানো যাক।

coin = [0, 2, 3, 6, 7]
অবশ্যই নোট গুলো লিস্ট এ ছোট থেকে বড় আকারে সাজানো থাকতে হবে।

এখানে 0 টাকা ও অ্যাড করা হয়েছে কারন আমরা অ্যারের ইনডেক্স ১ থেকে শুরু করতে চাচ্ছি। এর কি কারন তা পরে আপনাদের দেখাচ্ছি। আপনি চাইলে 0 র বদলে নাল ও রাখতে পারেন । যদিও 0 বা নাল কোনটাই আমাদের কোন কাজে আসবে না।

এখন আমরা একটা 2 dimensional অ্যারে বানাবো ।
arr [i] [j]
যেখানে  i হল মোট নোটের সংখ্যা। (আমাদের  উদাহরণ   এ  ০, ২, ৩, ৬, ৭ মোট  ৫ টি নোট)
এবং  j  হল মোট টাকার পরিমাণ। (আমাদের  উদাহরণ   এ  ১৩ টাকা)।

 বুঝার সুবিধার্থে নিচে একটি ডায়াগ্রাম দিলাম।

এখানে i এর মান যেসব ঘর এ 0 সেসব ঘর এ ইনফিনিটি বসাই।
এবং j এর মান যেসব ঘর এ 0  ( arr[0] [0] ছাড়া ) সেসব ঘর এ 0 বসাই।
তাহলে ছক তা নিচের মত দেখাবে......

এখন আসা করি বুঝতে পারছেন যে coin এর array তে আমরা 0 কেন  অ্যাড করেছিলাম।

coin এর array র ইনডেক্স এবং এই 2 dimensional array র ইনডেক্স same রাখার জন্য আমরা 0 অ্যাড করেছিইলাম। যদি ও 0 অ্যাড না করলে আমরা coin[ i - 1 ] ব্যাবহার করে কয়েন লিস্ট visit করতে পারতাম। কিন্তু coin [ i ] লিখলে বুঝতে বেশি সুবিধা হয়।
এখন কয়েন চেঞ্জ এর মুল আলগোরিদম এ আসা যাক ।

আমাদের এখন 2 dimensional array arr[i][j]  টি ফুল করতে হবে।।এবং এ ক্ষেত্রে আমরা একটি for লুপ এর ভিতরে আরেকটি inner for লুপ ব্যবহার করবো। এখন প্রতি ক্ষেত্রে আমরা arr[i][j] এর ভিতরে minimum of ( arr [i-1] [j] , arr [i] [j - coin [i] ] + 1) এর ভালুটি নিবো। কিন্তু যদি arr [ i ] [ j - coin [i] ]  এর ক্ষেত্রে j এর মান coin[ i ] এর চেয়ে ছোট হয় তাহলে আমরা j এর ক্ষেত্রে নেগেটিভ ভালু পাবো। সুতরাং সেই ক্ষেত্রে মিনিমাম বিবেচনা না করে শুধু মাত্র arr[i-1][j] এর ভালু টি ই নিব...।একটু বেশি হ য ব র ল হয়ে গেল মনে হয়...। একটা উদাহারণ দিলে বেপার টা পরিষ্কার হবে আসা করি...।

উপরের arr [ 1 ] [ 1 ] ঘর এর ক্ষেত্রেঃ
উল্লেখ্য এই row এর ক্ষেত্রে coin [ i ] বা coin [ 1 ] এর মান সর্বদা ই ২ টাকা হবে।

   arr[1][1] ঘর এর ক্ষেত্রে arr[ i - 1 ] [ j ] বা arr[ 1 - 1 ] [ 1 ] বা arr [ 0 ] [ 1 ] এর ভালু টি হল ইনফিনিটি ...।

এখন আবার  যদি আমরা arr[i][j-coin[i]]+1 বিবেচনা করি তাহলে  arr [i] [ j - coin[ i ] ] + 1 বা arr [ 1 ][ 1 - 2 ] + 1 ( যেহেতু coin[i] এর মান ২ ) বা arr[ 1 ] [ - 1 ] + 1 পাই... কিন্তু এরকম কোন index 2 dimensional array তে থাকে না। সুতরাং এই ক্ষেত্রে এই দুই ইনডেক্স এর মিনিমাম ভালু বিবেচনা করার দরকার নেই ।সরাসরি arr[ i - 1 ] [ j ] এর ভালু arr[ i ][ j ] তে বসবে...। উপরের ছক এ আমরা দেখছি যে arr[ i ] [ j ] ঘর এ একটি up arrow  কি দেওয়া আছে ।যেহেতু আমরা ভালু টি arr[i-1][j] থেকে বা বর্তমান ইনডেক্স এর উপরের ইনডেক্স থেকে পেয়েছি সেহেতু আমরা up arrow ব্যবহার করেছি। যদি আমরা ভালু টি arr[ i ] [ j - coin [ i ] ] + 1  থেকে পেতাম তাহলে আমরা '<'  কি টি ব্যবহার করতাম।
আরেকটি উদাহরণ দেখলে বিষয় টি আরো পরিষ্কার হবে...।

উপরের arr[ 1 ] [ 2 ] ঘর এর ক্ষেত্রে ঃ
    আগের বারের মতই এই row এর ক্ষেত্রে coin[i] বা coin[1] এর মান ২ টাকা হবে।

 arr[1][2] ঘর এর ক্ষেত্রে arr[ i - 1 ] [ j ] বা arr[ 1 - 1 ] [ 2 ] বা arr[ 0 ] [ 2 ] এর ভালু টি হল ইনফিনিটি ...।

এখন যদি আমরা  arr[ i ] [ j - coin [ i ] ] +1 বিবেচনা করি তাহলে  arr[ i ] [ j - coin[ i ] ] + 1 বা arr[ 1 ][ 2 - 2 ] + 1 ( যেহেতু coin[ i ] এর মান ২ ) বা  arr[ 1 ] [ 0 ] + 1 পাই... যার ভালু হলো 0+1 = 1

 এখানে প্রথম ক্ষেত্রে পাই আমরা ইনফিনিটি এবং দ্বিতীয় ক্ষেত্রে পাই  আমরা ১। minimum of (infinity, 1) থেকে আমরা ১ কে মিনিমাম হিসেবে পাই । যেহেতু এইখানে ১ ছোট সেহেতু arr[ 1 ] [ 2 ] এর মদ্ধে ১ বসেছে ।

এবং যেহেতু আমরা বাম পাস থেকে ভালু পেয়েছি এবার ,সেহেতু আমরা '<' কি ব্যবহার করেছি।।

এভাবে ই 2 dimensional array টির সব গুলো ঘর ফুল করতে হবে।যদি এমন কখন হয় যে
arr [ i - 1 ] [ j ] এবং arr [ i ] [ j - coin [ i ] ] + 1 উভয় এর মান সমান তাহলে arr [ i - 1 ] [ j ] থেকে মান আনতে হবে এবং up arrow ব্যাবহার করতে হবে

এখন চলুন সব গুলো ঘর পুরন করা যাক...।

এখন এত কষ্ট যার জন্য করলাম সেই ফলাফল পাওয়ার পালা...।

আমরা এখন backtracking শুরু করবো...। যেহেতু আমাদের ১৩ টাকা দরকার সেহেতু আমরা j=13 থেকে শুরু করবো এবং সর্বচ্চ নোট ৭ টাকার থেকে শুরু করার জন্য ইনডেক্স i = 4 থেকে শুরু করবো। অর্থাৎ আমরা প্রথম এ arr [ 4 ] [ 13 ] এ ভিসিট করব...।

এখন আমাদের দেখতে হবে যে আমরা যেই ইনডেক্স এ আছি ঐ ইনডেক্স এর arrow key কোন দিকে দেওয়া...। যদি arrow key == '<' হয় তাহলে আমরা coin [ i ] এর কয়েন টি একবার নিবো...।
এবং coin [ i ] এর ভালু র সমান লেফট এ শিফট করবো... । আর যদি  arrow key == ' ^ '  হয় তাহলে কোন কিছু পরিবর্তন না করে এক ঘর উপরে শিফট হয়ে যাব ।। এবং যখন আমরা j==0 তে এসে পরব তখন  backtracking বন্ধ করবো এবং যত গুলো কয়েন আমরা পাবো সেটা ই হল যে কতো টাকার নোট আমাদের কয়টা দরকার ।
তাহলে আমাদের উদাহরণ এর জন্য নিয়ম টি প্রয়োগ করে দেখা যাক... ।

এখানে arr[4][13]  এর  arrow key == '<' । সুতরাং আমরা coin[i] বা coin[4] এর ভালু তথা ৭ টাকার নোট টি একবার নিবো এবং ৭ ঘর বাম এ শিফট করবো। শিফট করার পর বর্তমান ইনডেক্স         arr [ 4 ] [ 13 - 7 ] বা arr [ 4 ] [ 6 ] এর arrow key == ' ^ '...। সুতরাং আমরা এক ঘর উপরে যাব...। এক ঘর উপরে যাওয়ার  পর বর্তমান ইনডেক্স arr [ 4 - 1 ] [ 6 ] বা arr [ 3 ] [ 6 ] এর arrow key == ' < '...।সুতরাং আমরা coin [ i ] বা coin [ 3 ] এর ভালু তথা 6 টাকার নোট টি একবার নিবো এবং 6 ঘর বাম এ শিফট করবো। শিফট করার পর বর্তমান ইনডেক্স arr [ 3 ] [ 6 - 6 ] বা arr [ 3 ] [ 0 ] যেখানে j == 0...। সুতরাং এখানে আমরা backtracking বন্ধ করবো।।তাহলে আমরা পেলাম ৭ টাকার নোট একটি এবং ৬ টাকার নোট একটি... যেখানে ৭ +৬  = ১৩...।

তো হয়ে গেলো বাবুল এর অ্যাপ বানানোর আলগোরিদম...।।

বিঃদ্রঃ আমার লেখা প্রথম অনলাইন ব্লগ এটি...।কোন ভুল হলে দয়া করে ক্ষমা সুন্দর দৃষ্টি তে দেখবেন... ধন্যবাদ...।