Longest Common Subsequence (LCS), Knapsack Problem গাইড ও নোট

১. Longest Common Subsequence (LCS)

Longest Common Subsequence (LCS) হল দুটি স্ট্রিং বা সিকোয়েন্সের মধ্যে এমন একটি দীর্ঘতম উপসিকোয়েন্স (subsequence) খোঁজা যা উভয় সিকোয়েন্সে বিদ্যমান থাকে এবং যেটি তাদের মধ্যে অর্ডার অনুসরণ করে।

উদাহরণ:

• স্ট্রিং 1: "ABCBDAB"
• স্ট্রিং 2: "BDCABB"
• LCS: "BCAB" (Longest Common Subsequence)

LCS Problem সাধারণত Dynamic Programming পদ্ধতিতে সমাধান করা হয়, যেখানে গ্রিড বা টেবিল তৈরি করে পূর্ববর্তী ফলাফল সংরক্ষণ করা হয়, যাতে একই সাব-সমস্যার পুনরাবৃত্তি না হয়।

উদাহরণ: LCS Algorithm in Java

public class LCS {
    public static int lcs(String str1, String str2) {
        int m = str1.length();
        int n = str2.length();
        
        // Create a table to store the lengths of longest common subsequence
        int[][] dp = new int[m + 1][n + 1];

        // Fill the table using dynamic programming approach
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1; // If characters match
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); // If characters don't match
                }
            }
        }

        return dp[m][n]; // The length of LCS is stored in dp[m][n]
    }

    public static void main(String[] args) {
        String str1 = "ABCBDAB";
        String str2 = "BDCABB";
        
        int result = lcs(str1, str2);
        System.out.println("Length of Longest Common Subsequence: " + result);
    }
}

ব্যাখ্যা:

• Dynamic Programming Table: এখানে একটি 2D অ্যারে dp ব্যবহার করা হয়েছে, যেখানে dp[i][j] মানটি প্রথম i চরিত্রের জন্য এবং প্রথম j চরিত্রের জন্য LCS এর দৈর্ঘ্য সংরক্ষণ করে।
• Recurrence Relation: যদি str1[i-1] == str2[j-1], তাহলে dp[i][j] = dp[i-1][j-1] + 1 (মানে তারা একটি লম্বা কমন সাবসিকোয়েন্স তৈরি করছে)। অন্যথায়, আমরা dp[i-1][j] এবং dp[i][j-1] এর মধ্যে বড় মান নেবো।

আউটপুট:

Length of Longest Common Subsequence: 4

Time Complexity: O(m * n), যেখানে m এবং n হল দুটি স্ট্রিংয়ের দৈর্ঘ্য।
Space Complexity: O(m * n), কারণ 2D টেবিল তৈরি করতে হয়।

২. Knapsack Problem

Knapsack Problem হল একটি Optimization Problem যেখানে আমাদের একটি নির্দিষ্ট ধারণক্ষমতা (capacity) সহ একটি বাক্স বা ব্যাগ (knapsack) দেওয়া থাকে এবং বিভিন্ন ওজন ও মানের বস্তু দেওয়া থাকে। আমাদের লক্ষ্য হল, সেই বস্তুগুলো নির্বাচন করা যেগুলির সম্মিলিত মান সর্বাধিক হয় এবং বস্তুগুলোর মোট ওজন দেওয়া ধারণক্ষমতার মধ্যে থাকে।

সমস্যার ধরন:

1. 0/1 Knapsack Problem: প্রতি বস্তুকে একবারই বেছে নেওয়া যেতে পারে।
2. Fractional Knapsack Problem: বস্তুগুলোর ভগ্নাংশও নেওয়া যেতে পারে।

এখানে আমরা 0/1 Knapsack Problem এর সমাধান করব, যা Dynamic Programming ব্যবহার করে সমাধান করা হয়।

উদাহরণ: 0/1 Knapsack Problem in Java

public class Knapsack {
    // Dynamic Programming solution for 0/1 Knapsack Problem
    public static int knapSack(int W, int[] wt, int[] val, int n) {
        int[][] dp = new int[n + 1][W + 1];

        // Build the table dp[][] in bottom up manner
        for (int i = 0; i <= n; i++) {
            for (int w = 0; w <= W; w++) {
                if (i == 0 || w == 0) {
                    dp[i][w] = 0; // If no items or no capacity, value is 0
                } else if (wt[i - 1] <= w) {
                    // If the item can be included in the knapsack
                    dp[i][w] = Math.max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w]);
                } else {
                    // If the item can't be included in the knapsack
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }

        return dp[n][W]; // Return the maximum value that can be achieved
    }

    public static void main(String[] args) {
        int[] val = {60, 100, 120}; // Values (profits)
        int[] wt = {10, 20, 30};   // Weights
        int W = 50;                 // Knapsack capacity
        int n = val.length;         // Number of items

        int result = knapSack(W, wt, val, n);
        System.out.println("Maximum value in Knapsack: " + result);
    }
}

ব্যাখ্যা:

• Dynamic Programming Table: 2D অ্যারে dp[i][w] ব্যবহার করা হয়েছে, যেখানে dp[i][w] হল প্রথম i বস্তু দিয়ে knapsack এর ধারণক্ষমতা w এর জন্য সর্বাধিক মান।
• Recurrence Relation:
  • যদি wt[i-1] <= w (যদি বর্তমান বস্তুটি knapsack এ ফিট হয়), তাহলে dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]], dp[i-1][w])।
  • অন্যথায়, dp[i][w] = dp[i-1][w]।

আউটপুট:

Maximum value in Knapsack: 220

Time Complexity: O(n * W), যেখানে n হল বস্তুগুলোর সংখ্যা এবং W হল knapsack এর ধারণক্ষমতা।
Space Complexity: O(n * W), কারণ একটি 2D ডিপি টেবিল ব্যবহার করা হয়।

সারাংশ

Longest Common Subsequence (LCS) এবং Knapsack Problem হল দুটি ক্লাসিক Dynamic Programming সমস্যার উদাহরণ, যেখানে প্রতিটি সমস্যা কিছু উপাদান নির্বাচন করে (যেমন, লংগেস্ট কমন সাবসিকোয়েন্স অথবা বস্তু নির্বাচন) এবং পূর্ববর্তী সিদ্ধান্তগুলির উপর ভিত্তি করে সর্বাধিক মান বা সমাধান খোঁজা হয়।

• LCS দুইটি স্ট্রিংয়ের মধ্যে সবচেয়ে দীর্ঘ সাধারণ উপসিকোয়েন্স বের করে।
• Knapsack Problem সীমিত ধারণক্ষমতায় সর্বাধিক মান সম্পন্ন বস্তু নির্বাচন করার সমস্যাকে সমাধান করে।

এই দুটি অ্যালগরিদমের মাধ্যমে, আপনি আরও জটিল সমস্যাগুলির জন্য Dynamic Programming কৌশল ব্যবহার করে কার্যকরী সমাধান পেতে পারেন।