একটি সিক্কার তালিকা C(c1, c2, ... Cn) এবং একটি মান V দেওয়া আছে। এখন সমস্যা হল ন্যূনতম কতগুলো সিক্কা ব্যবহার করে মান V তৈরি করা যায়।
নোট: ধরে নেওয়া হল সিক্কা C-এর অসীম সংখ্যা রয়েছে।
এই সমস্যায় আমরা বিবেচনা করব সিক্কার একটি সেট C{1, 2, 5, 10} দেওয়া আছে। প্রতিটি টাইপের অসীম সিক্কা আছে। অনুরোধকৃত মান পরিবর্তন করতে আমরা যেকোনো টাইপের ন্যূনতম সিক্কা নিতে চাইব। উদাহরণস্বরূপ, ২২ এর জন্য: {10, 10, 2} বেছে নেব, অর্থাৎ ৩টি সিক্কা ন্যূনতম।
ইনপুট এবং আউটপুট
ইনপুট: প্রয়োজনীয় মান। ধরা যাক ৪৮ আউটপুট: ন্যূনতম প্রয়োজনীয় সিক্কা। এখানে আউটপুট ৭। 48 = 10 + 10 + 10 + 10 + 5 + 2 + 1
অ্যালগরিদম
minCoins(coinList, n, value)
ইনপুট: বিভিন্ন সিক্কার তালিকা, সিক্কা সংখ্যা, দেওয়া মান।
আউটপুট: দেওয়া মান পाने کے জন্য ন্যূনতম সিক্কা সংখ্যা।
শুরু
যদি value = 0 হয়, তবে
ফেরত দিন 0
value+1 আকারের coins অ্যারে সংজ্ঞায়িত করুন, ∞ দিয়ে পূরণ করুন
coins[0] := 0
i := 1 থেকে value পর্যন্ত, করুন
j := 0 থেকে n পর্যন্ত, করুন
যদি coinList[j] <= i হয়, তবে
tempCoins := coins[i - coinList[j]]
যদি tempCoins ≠ ∞ এবং (tempCoins + 1) < coins[i] হয়, তবে
coins[i] := tempCoins + 1
끝난
끝난
coins[value] ফেরত দিন
শেষ
উদাহরণ (C++)
#include <iostream>
using namespace std;
int minCoins(int coinList[], int n, int value) {
int coins[value+1];
if(value == 0) return 0;
coins[0] = 0;
for (int i=1; i<=value; i++)
coins[i] = INT_MAX;
for (int i=1; i<=value; i++) {
for (int j=0; j> value;
cout << "Minimum " << minCoins(coins, n, value) << " coins required.";
return 0;
}
আউটপুট
Enter Value: 48 Minimum 7 coins required.
