> For the complete documentation index, see [llms.txt](https://phitron.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://phitron.gitbook.io/algorithm/unbounded-knapsack/_-coin-change-1.md).

# মডিউল ২১\_৪ঃ 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/>

কোডঃ&#x20;

```python
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)
```

<figure><img src="/files/CBuykbP9yjhPswj4M7ZB" alt=""><figcaption></figcaption></figure>

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

```cpp
#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;
}
```