মডিউল ২১_৪ঃ Coin Change 1

Coin Change 1 প্রব্লেমটিতে আপনাকে প্রথমে কিছু Coin দেয়া থাকবে।

Coin = [ 1, 2, 3 ]

এরপর আপনাকে একটা target দেয়া হবে। ধরেন Target = 5

এই প্রব্লেমে আপনাকে বের করতে হবে আপনি কতভাবে Target টি পেতে পারেন এবং এই প্রব্লেমের ক্ষেত্রে আপনি একটি Coin কে একাধিকবার ব্যবহার করতে পারবেন অথাথ এইটি unbounded knapsack subset sum এর মত।

উপরের ইনপুটটির জন্য আউটপুট হবে 5।

2 + 3 = 5

2 + 2 + 1 = 5

3 + 1 + 1 = 5

1 + 1 + 1 + 2 = 5

1 + 1 + 1 + 1 + 1 = 5

এই 5 ভাবেই Target টি পেতে পারি।

এখন আপনি এই প্রব্লেমটিকে Visualization করতে পারেন ।

ওয়েবসাইটঃ https://recursion.vercel.app/

কোডঃ

def fn(n, s):
  if n==0:
    if s==0: return 1;
    else: return 0;
  
  if coins[n-1]<=s:
    return fn(n, s-coins[n-1]) + fn(n-1, s)
  else:
    return fn(n-1, s)

সম্পূর্ণ কোডটি

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int w[n];
    for (int i = 0; i < n; i++)
    {
        cin >> w[i];
    }
    int s;
    cin >> s;
    int dp[n + 1][s + 1];
    dp[0][0] = 1;
    for (int i = 1; i <= s; i++)
        dp[0][i] = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= s; j++)
        {
            if (w[i - 1] <= j)
            {
                dp[i][j] = dp[i][j - w[i - 1]] + dp[i - 1][j];
            }
            else
            {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    cout << dp[n][s] << endl;
    return 0;
}