ন্যূনতম সংখ্যক কয়েন খুঁজে পেতে লোভী অ্যালগরিদমের জন্য C/C++ প্রোগ্রাম

একটি লোভী অ্যালগরিদম হল একটি অ্যালগরিদম যা প্রদত্ত সমস্যার জন্য একটি সর্বোত্তম সমাধান খুঁজে পেতে ব্যবহৃত হয়। লোভী অ্যালগরিদম প্রতিটি অংশের স্থানীয়ভাবে সর্বোত্তম সমাধান (সমস্যার একটি অংশের জন্য সর্বোত্তম সমাধান) খুঁজে বের করে কাজ করে তাই দেখায় যে বিশ্বব্যাপী সর্বোত্তম সমাধান পাওয়া যেতে পারে।

এই সমস্যায়, আমরা একটি লোভী অ্যালগরিদম ব্যবহার করব ন্যূনতম সংখ্যক কয়েন/নোট যা প্রদত্ত যোগফলের সাথে মেকআপ করতে পারে৷ এর জন্য আমরা সমস্ত বৈধ মুদ্রা বা নোট যেমন {1, 2, 5, 10, 20, 50, 100, 200, 500, 2000} মূল্যবোধ বিবেচনা করব৷ এবং আমাদের এই কয়েন/নোটের সংখ্যা ফেরত দিতে হবে যা আমাদের যোগফল পর্যন্ত করতে হবে।

প্রসঙ্গটি আরও ভালভাবে বোঝার জন্য কয়েকটি উদাহরণ নেওয়া যাক -

উদাহরণ 1 −

ইনপুট :1231 আউটপুট :7

ব্যাখ্যা − আমাদের লাগবে দুটি 500 টাকার নোট, দুটি 100 টাকার নোট, একটি 20 টাকার নোট, একটি 10 ​​টাকার নোট এবং একটি 1 টাকার কয়েন। এর যোগফল 2+2+1+1+1 =7

উদাহরণ 2 −

ইনপুট:2150আউটপুট:3

ব্যাখ্যা − আমাদের একটি 2000 টাকার নোট, একটি 100 টাকার নোট এবং একটি 50 টাকার নোট লাগবে৷

একটি লোভী অ্যালগরিদম ব্যবহার করে এই সমস্যাটি সমাধান করতে, আমরা খুঁজে পাব কোনটি ব্যবহার করা যেতে পারে সবচেয়ে বড়। তারপর আমরা যোগফল থেকে বৃহত্তম মূল্য বিয়োগ করব এবং যোগফল শূন্য না হওয়া পর্যন্ত একই প্রক্রিয়াটি আবার করব৷

অ্যালগরিদম

উদাহরণ

#include নামস্পেস ব্যবহার করে / sizeof(notes[0]);void minchange(int sum){ vector coins; জন্য (int i =n - 1; i>=0; i--) { যখন (sum>=নোট[i]) { যোগ -=নোট[i]; coins.push_back(নোট[i]); } } এর জন্য (int i =0; i  
আউটপুট
 
কয়েন/নোটের ন্যূনতম সংখ্যা যার যোগফল 3253 হল 2000 500 500 200 50 2 1