Coin Change Problem Using Dynamic Programming

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <conio.h>
#include <climits>
#include <cstring>

using namespace std;

int main ()
{
    int amount;
    int b[10000];
    memset(b, INT_MAX, sizeof b);
    b[0]=0;
    int a[20];
    int coin;
    int i;
    cout << "amount : " ;
    cin >> amount;
    cout << "No of coin : " ;
    cin >> coin;
    for(i=0; i<coin; i++){
        cin >> a[i];
    }

     for(int i = 0; i <amount; i++)
    {
        for(int j = a[i] ; j <= amount; j++)
        {
            int pre = b[j];
            int cur = 1+b[j-a[i]];
            b[j] = min(pre,cur);
        }
    }
     cout << b[amount];

getch();
return 0;
}

The Activity Selection Problem With Greedy Algorithom

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <conio.h>

using namespace std;

struct activity{
double s;
double e;
double c;
};

bool compare(activity p1, activity p2){
if(p1.e<p2.e)
return true;
else
return false;
}

int main(){
activity p[100];
int n,i;
int start,End;
int count = 1;
scanf("%d",&n);
for(i=0;i<n;i++){
cin>>start;
cin>>End;
p[i].s = start;
p[i].e = End;
}
sort(p,p+n, compare);

int j= 0;
for(i=1; i<n; i++){
        if(p[i].s >= p[j].e){
            count ++;
            j=i;
        }
}
cout << "Activity : "<<count<<endl;

getch();
return 0;
}

The Fractional Knapsack Problem With Greedy Algorithom

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <conio.h>


using namespace std;

struct Product{
double b;
double w;
double v;
double c;
};

bool compare(Product p1, Product p2){
if(p1.v>p2.v){
return true;
}
else{
return false;
}
}

int main(){
Product p[100];
int n,i;
double w,b,v;
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%lf",&w);
scanf("%lf",&b);
p[i].w = w;
p[i].b = b;
p[i].v = b/w;
}
sort(p,p+n, compare);

int k=10,f=0,t=0;
for(i=0;i<n;i++){
        p[i].c=0;
}
i=0;
while(f<k){
        if(p[i].w <=(k-f)){
            t += p[i].b;
            f += p[i].w;
            p[i].c = p[i].w;
        }
        else{
            t += (k-f)*p[i].v;
            p[i].c = k-f;
             f += k-f;
        }
        i++;
}
cout <<"Total profit  :  " <<t << " $\n";

for(i=0;i<n;i++)
        cout << p[i].c << " \n";

getch();
return 0;
}

Disjoint-set data structure

#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iostream>

using namespace std;

int arry[100];

int makeset(int x){
    arry[x]=x;
}

int found(int x){
    if(x==arry[x])
        return x;
    return found(arry[x]);
}

int Union(int x,int y){
    int s1=found(x);
    int s2=found(y);
    if(s1!=s2){
        arry[s2]=s1;
        cout<<"Union between "<<x<<" & "<<y<<endl;
    }
    else
        cout<<"sorry, They are in same set\n";
}


int main()
{

    cout << "Please input your choice\n1. Make Set\n2. Union\n3. Find\n4. End"<< endl;
    while(1){
        cout << "Please input your choice : ";
        int n;
        cin>>n;
        switch(n)
        {
            case 1 : int a;
                     cout<< "Enter element : ";
                     cin>>a;
                     makeset(a);
                     break;
            case 2 : int x,y;
                     cout<< "Enter two element for union : ";
                     cin>>x>>y;
                     Union(x,y);
                     break;
            case 3 : int z;
                     cout<< "Enter find element : ";
                     cin>>z;
                     cout<< "Set no : "<< found(z) <<endl;
                     break;
            case 4 : return 0;
                     break;
            default : cout<<"Wrong input..... Try again"<<endl;
        }
    }

    return 0;
}

The Maximum Subarray

Problem link (Click Here)

#include <iostream>
#include <cstdio>
#include<cstdlib>
#include <string>
#include <cstring>
#include <algorithm>
#include <climits>
#include <vector>

using namespace std;

int arry[1000000];

int maxoverlap(int f, int m, int l){
 int m1= INT_MIN;
    int s=0;
    for(int i=m; i>=f; i--){
        s+=arry[i];
        m1 = max(m1, s);
    }
 int m2= INT_MIN;
    s=0;
    for(int i=m+1; i<=l; i++){
        s+=arry[i];
        m2 = max(m2, s);
    }
    return m1+m2;
}

int maxsum(int f, int l){
 if(f==l) return arry[f];
 int lmax;
 int rmax;
 int over;
    if(f<l){
        int m = (f+l)/2;
         lmax = maxsum(f,m);
         rmax = maxsum(m+1,l);
         over = maxoverlap(f,m,l);

    }
    return max(max(lmax,rmax),over);
}


int main()
{
    int t;
    cin>> t;
    while(t--){
        int n;
        cin>>n;
        for(int i=0;i<n;i++){
            cin>>arry[i];
        }
        int maxs = maxsum(0, n-1);
        int a=0;
        for(int i=0;i<n;i++){
            if(arry[i]>=0){
                a+=arry[i];
            }
        }
        cout << maxs <<" "<< a << endl;
    }

    return 0;
}

Free Bambooo Bank Limited

Problem link(Click Here)

#include <iostream>
#include <cstdio>
#include<cstdlib>
#include <string>
#include <cstring>
#include <algorithm>
#include <climits>
#include <vector>

using namespace std;

int main()
{
    int o[100];
    int e[100];
    int a[100];
    int n,t=0;
    int wc=3;
    int odd=0,even=0;
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>a[i];
        if(a[i]%2==0)
            even++;
        else
            odd++;
    }
    int j=0;
    int k=0;
    for(int i=0;i<n;i++){
        if(a[i]%2==0){
            e[j]=a[i];
            j++;
        }
        else{
            o[k]=a[i];
            k++;
        }
    }
    int count=0;
    for(int i=0; i<odd-1; i++){
        if(o[i]>o[i+1])
            count++;
    }
     for(int i=0; i<even-1; i++){
        if(e[i]>e[i+1])
            count++;
    }
    t=even/wc;
    t=t+odd/wc;
    cout<< t << endl ;
    if(count==0)
        cout<<"OK"<< endl;
    else
        cout<<"NOT OK"<< endl;

    return 0;
}