মডিউল ২১_৫ঃ Coin Change 2

Coin Change 1 প্রব্লেমটি বুঝে থাকলে আপনি খুব সহজেই Coin Change 2 প্রব্লেমটি বুঝতে পারবেন।

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

এখন Coin Change 2 প্রব্লেমটিতে আপনাকে বলা হয় কত কম Coin ব্যবহার করে আপনি Target টি পেতে পারেন।

উপরে আমরা দেখছি Target = 5 পেতে সবচেয়ে কম সংখ্যক Coin ব্যবহার হয়েছে 2 + 3 = 5 এর মধ্যে, যেখানে 2 টি

Coin ব্যবহার হয়েছে।

সম্পূর্ণ কোড

#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] = 0;
    for (int i = 1; i <= s; i++)
        dp[0][i] = INT_MAX - 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= s; j++)
        {
            if (w[i - 1] <= j)
            {
                dp[i][j] = min(1 + dp[i][j - w[i - 1]], dp[i - 1][j]);
            }
            else
            {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    // for (int i = 0; i <= n; i++)
    // {
    //     for (int j = 0; j <= s; j++)
    //     {
    //         cout << dp[i][j] << " ";
    //     }
    //     cout << endl;
    // }
    if (dp[n][s] == INT_MAX - 1)
        cout << "Not Possible" << endl;
    else
        cout << dp[n][s] << endl;
    return 0;
}