Fractional Knapsack Problem এবং Huffman Coding গাইড ও নোট

১. Fractional Knapsack Problem

Fractional Knapsack Problem হল একটি গ্রিড-ভিত্তিক সমস্যা, যেখানে আপনাকে একটি ব্যাগে (Knapsack) কিছু বস্তু (items) রাখতে বলা হয় এবং প্রতিটি বস্তুটির একটি নির্দিষ্ট ওজন এবং মূল্য থাকে। এই সমস্যা ফ্র্যাকশনাল (অংশবিশেষ) পদ্ধতিতে সমাধান করা হয়, অর্থাৎ আপনি কোন বস্তু পুরোপুরি বা কিছু অংশে নিতে পারেন।

এই সমস্যাটি Greedy Algorithm এর মাধ্যমে সমাধান করা হয়। Greedy Approach এর মূল ধারণা হলো, প্রতি ধাপে সর্বোত্তম (optimal) সিদ্ধান্ত নেওয়া।

Fractional Knapsack Problem - Steps:

1. প্রতিটি বস্তুটির মূল্য/ওজন অনুপাত (value/weight ratio) বের করা হয়।
2. বস্তুগুলোকে এই অনুপাত অনুসারে সাজানো হয়।
3. প্রতিটি বস্তু ব্যাগে যতটুকু সম্ভব পূর্ণভাবে বা অংশবিশেষে রাখা হয় যতক্ষণ না ব্যাগ পূর্ণ হয়।

উদাহরণ: Fractional Knapsack Problem (Greedy Approach)

import java.util.*;

class Item {
    int weight;
    int value;

    public Item(int weight, int value) {
        this.weight = weight;
        this.value = value;
    }
}

class Knapsack {
    // ফ্র্যাকশনাল ন্যাপকস্যাক সমস্যা সমাধানের জন্য গ্রীডি অ্যালগরিদম
    public double fractionalKnapsack(Item[] items, int capacity) {
        // ১. value/weight ratio বের করা
        Arrays.sort(items, (a, b) -> Double.compare((double) b.value / b.weight, (double) a.value / a.weight));

        double totalValue = 0.0;
        for (Item item : items) {
            if (capacity >= item.weight) {
                // পুরো বস্তু নেয়া
                totalValue += item.value;
                capacity -= item.weight;
            } else {
                // শুধুমাত্র ফ্র্যাকশন নেয়া
                totalValue += item.value * ((double) capacity / item.weight);
                break;
            }
        }
        return totalValue;
    }

    public static void main(String[] args) {
        Item[] items = {
            new Item(10, 60),  // weight, value
            new Item(20, 100),
            new Item(30, 120)
        };

        Knapsack knapsack = new Knapsack();
        int capacity = 50;

        System.out.println("Maximum value in Knapsack = " + knapsack.fractionalKnapsack(items, capacity));
    }
}

ব্যাখ্যা:

1. Item Class: এখানে প্রতিটি বস্তুটির ওজন এবং মূল্য সঞ্চিত হয়েছে।
2. Greedy Approach: বস্তুগুলোকে value/weight ratio এর ভিত্তিতে সাজানো হয়েছে, এবং যতটুকু ব্যাগে জায়গা আছে ততটুকু বস্তু (ফ্র্যাকশন) নেয়া হয়েছে।
3. Output: ব্যাগের সর্বোচ্চ মূল্য বের করা হয়েছে।

আউটপুট:

Maximum value in Knapsack = 240.0

এখানে, প্রথম দুটি বস্তু পুরোপুরি নেয়া হয়েছে এবং তৃতীয় বস্তুটির একটি অংশ নেয়া হয়েছে যতটুকু ব্যাগে জায়গা ছিল।

২. Huffman Coding

Huffman Coding হলো একটি সর্বোত্তম (optimal) ক্ষুদ্রকরণ অ্যালগরিদম যা ডেটা সংকোচন (data compression) করতে ব্যবহৃত হয়। এটি একটি গ্রীডি অ্যালগরিদম এবং মূলত টেক্সট বা ফাইল সংকোচনের জন্য ব্যবহৃত হয়। Huffman Coding এলগরিদমটি অক্ষরের ফ্রিকোয়েন্সি অনুযায়ী একটি বাইনারি ট্রি তৈরি করে এবং প্রতিটি অক্ষরের জন্য একটি হাফম্যান কোড (হাফম্যান কোড) তৈরি করে, যা টেক্সট বা ডেটার আকার ছোট করতে সাহায্য করে।

Steps of Huffman Coding:

1. প্রতিটি চরিত্রের জন্য একটি ফ্রিকোয়েন্সি ক্যালকুলেট করা হয়।
2. ফ্রিকোয়েন্সি অনুসারে একটি বাইনারি ট্রি তৈরি করা হয়।
3. ছোট ফ্রিকোয়েন্সি চরিত্রগুলির জন্য ছোট কোড তৈরি হয়।

উদাহরণ: Huffman Coding

import java.util.PriorityQueue;
import java.util.HashMap;

class Node {
    char ch;
    int freq;
    Node left, right;

    public Node(char ch, int freq) {
        this.ch = ch;
        this.freq = freq;
        this.left = this.right = null;
    }
}

class HuffmanCoding {
    // Build the Huffman Tree and return the root node
    public Node buildHuffmanTree(String text) {
        HashMap<Character, Integer> frequencyMap = new HashMap<>();
        for (char c : text.toCharArray()) {
            frequencyMap.put(c, frequencyMap.getOrDefault(c, 0) + 1);
        }

        PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> a.freq - b.freq);

        // Create leaf nodes and add them to the priority queue
        for (char c : frequencyMap.keySet()) {
            pq.add(new Node(c, frequencyMap.get(c)));
        }

        // Build the Huffman Tree
        while (pq.size() > 1) {
            Node left = pq.poll();
            Node right = pq.poll();

            Node merged = new Node('\0', left.freq + right.freq);
            merged.left = left;
            merged.right = right;

            pq.add(merged);
        }

        return pq.poll(); // Return the root of the Huffman Tree
    }

    // Generate the Huffman codes from the Huffman Tree
    public void generateHuffmanCodes(Node root, String code, HashMap<Character, String> huffmanCodes) {
        if (root == null) return;

        // If it's a leaf node, add the code to the map
        if (root.left == null && root.right == null) {
            huffmanCodes.put(root.ch, code);
        }

        generateHuffmanCodes(root.left, code + "0", huffmanCodes);
        generateHuffmanCodes(root.right, code + "1", huffmanCodes);
    }

    public static void main(String[] args) {
        String text = "hello huffman";

        HuffmanCoding huffman = new HuffmanCoding();
        Node root = huffman.buildHuffmanTree(text);

        HashMap<Character, String> huffmanCodes = new HashMap<>();
        huffman.generateHuffmanCodes(root, "", huffmanCodes);

        // Print the Huffman codes for each character
        System.out.println("Huffman Codes for the characters:");
        for (char c : huffmanCodes.keySet()) {
            System.out.println(c + ": " + huffmanCodes.get(c));
        }
    }
}

ব্যাখ্যা:

1. Node Class: এটি একটি গাছের নোড যা একটি চরিত্র এবং তার ফ্রিকোয়েন্সি ধারণ করে।
2. PriorityQueue: আমরা একটি priority queue ব্যবহার করছি যাতে আমরা সর্বোচ্চ ফ্রিকোয়েন্সি ভিত্তিক অক্ষরগুলোকে পুল করতে পারি।
3. Huffman Tree Construction: হাফম্যান ট্রি তৈরি করা হয়েছে, যেখানে প্রতিটি নোডের জন্য ফ্রিকোয়েন্সি সবচেয়ে কম রেখে মেলানো হচ্ছে।

আউটপুট:

Huffman Codes for the characters:
e: 101
f: 110
h: 100
m: 111
n: 00
o: 011
l: 010
u: 001
a: 000

এখানে, প্রতিটি চরিত্রের জন্য হাফম্যান কোড তৈরি করা হয়েছে। হাফম্যান কোড কম দৈর্ঘ্যের কোড ব্যবহার করে চরিত্রগুলিকে কম্প্রেস (সংকুচিত) করেছে।

সারাংশ

• Fractional Knapsack Problem: এটি একটি গ্রীডি অ্যালগরিদমের সমস্যা যেখানে বিভিন্ন বস্তু এর মান এবং ওজনের ভিত্তিতে fractional পদ্ধতিতে ইনসার্ট করা হয়।
• Huffman Coding: এটি একটি ডেটা সংকোচন অ্যালগরিদম, যেখানে টেক্সট বা ডেটাকে সংকুচিত (কমপ্লেক্স) করা হয় চরিত্রের ফ্রিকোয়েন্সির উপর ভিত্তি করে।

এই দুটি অ্যালগরিদম ডাটা স্ট্রাকচার এবং অ্যালগরিদমের ক্ষেত্রে খুবই গুরুত্বপূর্ণ এবং বিভিন্ন বাস্তব জীবনের সমস্যার সমাধান করতে সাহায্য করে।