Fibonacci Series, Knapsack Problem এর Dynamic Programming ইমপ্লিমেন্টেশন

Fibonacci Series এবং Knapsack Problem এর Dynamic Programming ইমপ্লিমেন্টেশন

1. Fibonacci Series (Dynamic Programming)

ফিবোনাচ্চি সিরিজ হল একটি সিকোয়েন্স যেখানে পরবর্তী সংখ্যাটি আগের দুটি সংখ্যার যোগফল। এই সিরিজটি সাধারণত এইভাবে শুরু হয়:
\[ F(0) = 0, F(1) = 1 \]
আর এরপরের সবগুলো সংখ্যা হচ্ছে:
\[ F(n) = F(n-1) + F(n-2) \]

যদিও এটি রিকার্সিভভাবে সোজা সোজা সমাধান করা যায়, তবে তা কার্যকরী নয়, কারণ এটি অনেক পুনরাবৃত্তি করে। এখানে Dynamic Programming ব্যবহার করে কার্যকরভাবে এটি সমাধান করা যায়।

Fibonacci Series - Dynamic Programming ইমপ্লিমেন্টেশন:

#include <stdio.h>

// Fibonacci using Dynamic Programming (Tabulation)
long long fibonacci(int n) {
    long long dp[n+1];
    
    // Base cases
    dp[0] = 0;
    dp[1] = 1;

    // Fill the dp array iteratively
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    
    return dp[n];
}

int main() {
    int n;
    printf("Enter the number to find Fibonacci: ");
    scanf("%d", &n);
    
    printf("Fibonacci number at position %d is: %lld\n", n, fibonacci(n));
    
    return 0;
}

Output Example:

Enter the number to find Fibonacci: 10
Fibonacci number at position 10 is: 55

Fibonacci Dynamic Programming-এর সুবিধা:

• Time Complexity: O(n), কারণ প্রতিটি উপাদান একবারের জন্য হিসাব করা হয়।
• Space Complexity: O(n), কারণ আমরা একটি অ্যারে ব্যবহার করছি সবার মান রাখার জন্য।

2. Knapsack Problem (0/1 Knapsack) - Dynamic Programming

Knapsack Problem একটি ক্লাসিক্যাল অপটিমাইজেশন সমস্যা যেখানে আমাদের একটি সীমিত ধারণক্ষমতার ব্যাগ (Knapsack) আছে এবং কিছু আইটেম দেয়া আছে, যেগুলোর নির্দিষ্ট মান (value) এবং ওজন (weight) রয়েছে। আমাদের উদ্দেশ্য হল এমন আইটেমগুলি নির্বাচন করা যাতে তাদের মোট ওজন ব্যাগের ধারণক্ষমতার মধ্যে থাকে এবং তাদের মোট মান সর্বাধিক হয়।

Problem Definition (0/1 Knapsack):

• আমাদের কাছে Nটি আইটেম, প্রতিটির একটি ওজন \( w[i] \) এবং একটি মান \( v[i] \)।
• আমাদের কাছে একটি ব্যাগ, যার ধারণক্ষমতা \( W \)।
• আমাদের কাজ হল এমন আইটেমগুলো নির্বাচন করা যাতে ব্যাগের ওজন \( W \)-এর মধ্যে থাকে এবং তাদের মান সর্বাধিক হয়।

Knapsack Problem - Dynamic Programming ইমপ্লিমেন্টেশন:

#include <stdio.h>

// Knapsack Problem using Dynamic Programming
int knapsack(int W, int w[], int v[], int n) {
    int dp[n+1][W+1]; // DP table to store solutions to subproblems

    // Fill the DP table
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= W; j++) {
            if (i == 0 || j == 0) {
                dp[i][j] = 0; // Base case: no items or capacity is 0
            } else if (w[i-1] <= j) {
                // If the item can be included in the current capacity
                dp[i][j] = (v[i-1] + dp[i-1][j-w[i-1]]) > dp[i-1][j] ?
                            (v[i-1] + dp[i-1][j-w[i-1]]) : dp[i-1][j];
            } else {
                // If the item can't be included
                dp[i][j] = dp[i-1][j];
            }
        }
    }

    // The last cell contains the maximum value
    return dp[n][W];
}

int main() {
    int n, W;

    // Input number of items and knapsack capacity
    printf("Enter number of items: ");
    scanf("%d", &n);
    printf("Enter capacity of knapsack: ");
    scanf("%d", &W);

    int weights[n], values[n];

    // Input weights and values of items
    printf("Enter weights of items: ");
    for (int i = 0; i < n; i++) {
        scanf("%d", &weights[i]);
    }

    printf("Enter values of items: ");
    for (int i = 0; i < n; i++) {
        scanf("%d", &values[i]);
    }

    // Call knapsack function and display the result
    printf("Maximum value in knapsack = %d\n", knapsack(W, weights, values, n));
    
    return 0;
}

Output Example:

Enter number of items: 4
Enter capacity of knapsack: 5
Enter weights of items: 1 2 3 8
Enter values of items: 20 5 10 40
Maximum value in knapsack = 60

Knapsack Dynamic Programming-এর সুবিধা:

• Time Complexity: O(n * W), যেখানে n হল আইটেমের সংখ্যা এবং W হল ব্যাগের ধারণক্ষমতা।
• Space Complexity: O(n * W), কারণ ডিপি টেবিলের সাইজ হলো \( n \times W \)।

সারসংক্ষেপ:

1. Fibonacci Series:
   • Dynamic Programming ব্যবহার করে Fibonacci সিরিজের মান দ্রুত ও কার্যকরভাবে বের করা যায়। এতে মেমরি ব্যবহার সঠিকভাবে নিয়ন্ত্রণ করা হয় এবং সময় জটিলতা O(n) এ কমিয়ে আনা হয়।
2. Knapsack Problem:
   • 0/1 Knapsack সমস্যা সমাধান করতে Dynamic Programming ব্যবহার করা হয়, যাতে সীমিত ধারণক্ষমতা সহ সর্বাধিক মান পাওয়া যায়। এর সময় জটিলতা O(n * W) এবং স্পেস জটিলতা O(n * W), যেখানে n হল আইটেমের সংখ্যা এবং W হল ব্যাগের ধারণক্ষমতা।