Dynamic Programming - 1 ( Coin change )

একটা বড় problem কে ছোট ছোট ভাগে ভাগ করে সেগুলো solve করার মাধ্যমে বড় problem টাকে solve করাই হচ্ছে Dynamic programming এর কাজ। আমরা প্রথমে কিছু সহজ DP প্রবলেম শিখব। আমরা আজকে যা শিখব তা হল coin change টাইপ প্রবলেম।

Type -1 ( Unlimited Coin )

শিখব কই থেকেঃ

See this slide

#define MAX 10000

vector<int>coin; // contains coin value
int is_possible[MAX];
int coin_need[MAX];

int coin_change(int need_to_make) // need_to_make < MAX
{
    // fill coin_need with INF value here

    is_possible[0] = 1;
    coin_need[0] = 0;

    for(int i=0;i<coin.size();i++)
    {
        for(int j=0;j+coin[i]<MAX;j++)
        {
            if(is_possible[j])
            {
                int next = j+coin[i];

                is_possible[ next ] = 1;
                coin_need[ next ] = min( coin_need[j]+1 , coin_need[ next ] );
            }
        }
    }
    return coin_need[need_to_make];
}

Type - 2 ( Limited Coin )

এখন তোমাকে যদি কিছু coin দেয়া হয় এবং বলে দেয়া হয় কোন coin টা maximum কয়বার ব্যবহার করতে পারবে তখন কি করবে?

আমরা unlimited  coin  এর জন্যে যেভাবে বাম থেকে ডানে লুপ চালিয়েছি, এবার একই ভাবে ডান থেকে বামে লুপ চালাব। তাহলেই limited coin এর জন্যে answer পেয়ে যাব।

#define MAX 10000

struct coin{
    int val,how_many;
};

vector<coin>has_coin;
bool is_possible[MAX];
int minimum_coin_need[MAX];


int limited_coin_change(int need_to_make)
{
    is_possible[0] = true;
    minimum_coin_need[0] = 0;

    for(int i=0;i<has_coin.size();i++)
    {
        for(int j= MAX-1 ; j>=0 ; j--)
        {
            if(is_possible[j] == true)
            {
                int value = has_coin[i].val;
                int next = j + value;
                int curent = j;

                for(int k=0;k<has_coin[i].how_many;k++)
                {
                    is_possible[next] = true;
                    minimum_coin_need[next] = min(minimum_coin_need[curent]+1,minimum_coin_need[next]);

                    curent = next;
                    next = next+value;
                }
            }
        }
    }

    return minimum_coin_need[need_to_make]; // return desire result
}

Problem

UVA - 147, 166, 357, 674, 10313, 10306, 11137, 11517, 562

Lightoj - 1231, 1232, 1233

Recursion & Backtracking

Recursion, programming এর জন্যে খুব গুরুত্বপূর্ণ। recursion প্রথম দিকে শেখার সময় অনেকের কাছে কঠিন লাগে। কিন্তু একবার শিখে ফেলতে পারলে এর থেকে সহজ আর কিছু নেই। শুধু শেখার আগ পর্যন্ত লেগে থাকতে হবে।

কোথা থেকে শিখব?

দেখতেই হবেঃ

1. ফাহিম ভাইয়ের ব্লগ। খুবই সুন্দর করে লিখেছেন। 
2. যোবায়ের ভাইয়ের ব্লগ। Attacking recursion.

আরো কিছু দেখতে পারোঃ

1. Topcoder
2. আর একটা...

করতেই হবেঃ

Problems of recursion.  এখানে ২০ টা problem দেয়া আছে। এই ২০ টা অবশ্যই করতে হবে। এই গুলো নিজে যখন বুঝে করতে পারবে তখনি শুধু নিচের গুলো করার চেষ্টা করবে।

Problem

এখানে যে problem গুলো দেয়া হয়েছে তা ফরহাদ ভাই ( 07 Batch, SUST & WF of 11,12 ) আমাদের training camp এ করিয়েছিলেন। সেখান থেকে সবগুলো problem দিয়ে দিলাম।

Lightoj - 1023, 1117

Uva - 195, 10696, 10776, 11753, 624

TopCoder - SRM 491 Div 2 1000, TCHS SRM 16 1000, TCHS SRM 55 1000, SRM 273 div 2 1000, TCHS SRM 2 1000, SRM 449 Div 2 500, TCCC06 online Round 2A Div 1 250, SRM 275 Div 2 500, TCHS SRM 26 500

TJU - 1306, 2893

All Pairs Shortest Path (Floyd–Warshall)

Floyd Warshall একটা গ্রাফের প্রতিটা নোড থেকে প্রতিটা নোডের দূরত্ব বের করে। খুব সহজ। এখনি নেটে সার্চ দাও। একবার দেখলেই পেরে যাবে। :)

#define MAX 100
#define INF (1<<30) // 2^30

int dis[MAX][MAX]; // distance

void floyd_warshall()
{
    for(int i=0;i<MAX;i++)
    {
        for(int j=0;j<MAX;j++)
        {
            if(i==j) dis[i][j] = 0; // distance from a node to itself is 0
            else dis[i][j] = INF; // initially distance from node i to j is INF
        }
    }

    /*

    here construct the graph with distance
    If a connection exists between node 2 and 5 with distance 8, update

    dis[2][5] = 8;
    dis[5][2] = 8;

    */
    
// ****************  Floyd Warshall *******************
    for(int k=0;k<MAX;k++)
    {
        for(int i=0;i<MAX;i++)
        {
            for(int j=0;j<MAX;j++)
            {
                dis[i][j] = min(dis[i][j],dis[i][k]+dis[k][j]);
            }
        }
    }
    return ;
}

Problem

UVA - 821, 341, 534, 10048, 544

Single source shortest path ( SSSP - Dijkstra )

কোন গ্রাফের একটা নোড থেকে আরেকটা নোড এর মিনিমাম দূরত্ব বের করাই  dijkstra এর কাজ।
অনলাইনে সার্চ দিলেই ভাল ভাল টিওটোরিয়াল পাবে শেখার জন্যে।
Dijkstra animation

শিখতে হবেঃ

• STL
  1. Priority Queue ( push, pop, top, size, empty )
  Priority Queue একটি Data structure যেখানে element গুলো সবসময়  sorted থাকে।
  Priority Queue কি ও কি করে শুধু সেটা জানলেই হবে আপাতত। Data structure কোর্স করার সময় বিস্তারিত তখন জানতে পারবে।
  

#define SZ(a) (int)a.size()

#define MAX 1000
#define INF (1<<30) // 2^30

struct data{
    int v,w;

    // how the data'll be sorted in priority queue
    bool operator<(const data &p)const
    {
        return p.w<w; // in ascending order
    }
};

/*
You don't need to understand how does the following function work in the
structure right now.

bool operator<(const data &p)const
{
    return p.w<w;
}

You'll understand it later. Only remember if you write
return p.w<w; // It'll sort in ascending order of w
return p.w>w; // It'll sort in descending order of w
*/

vector<data>con[MAX]; // graph connection
int dis[MAX]; // distance from the start node

int dijkstra(int start,int end)
{

    priority_queue<data>Q;
    for(int i=0;i<MAX;i++) dis[i] = INF; 
    // at first set infinite distance from start node to every node 

    data tmp;
    tmp.v = start;
    tmp.w = 0;
    pq.push(tmp);
    dis[start] = 0;

    while(!Q.empty())
    {
        int u = Q.top().v;
        int w_u = Q.top.w;
        Q.pop();

        // if(u==end) return dis[end]; It works also;

        for(int i=0;i<SZ(con[u]);i++)
        {
            int v = con[u][i].v;
            int w_v = con[u][i].w;

            if( w_u+w_v < dis[v] )
            {
                dis[v] = w_u + w_v;

                tmp.v = v;
                tmp.w = dis[v];

                pq.push(tmp);
            }
        }
    }

    return dis[end];
}

Problem

UVA - 341, 920, 10801, 10986, 10000