HackerEarth: City and Campers 2 (DSU-UnionFind)

SIMPLE DP-Knapsack Problem solution:

Problem:

We have given n-items each ni with weight w[i] and we can get profit v[i] from each item.

 Size of our Knapsack is only W. We have to maximize profit as much as possible as much as 

using low Knapsack size.

Solution:-

#include<bits/stdc++.h>
#define fr(i,a,n) for(i=a;i<=n;i++)
#define SET(a) memset(a,-1,sizeof(a))
using namespace std;
typedef long long ll;

int n,W,dp[102][505],w[102],v[102];

int main()
{
    int i,j,mxfn,mncst;
    while(cin>>W>>n && (W && n))
    {
        fr(i,1,n)
        {
            cin>>w[i]>>v[i];
        }

        fr(i,0,n-1)dp[i][0]=0;
        fr(j,0,W)dp[0][j]=0;
        mxfn=0;
        mncst=INT_MAX;
        fr(i,1,n)
        {
            fr(j,1,W)
            {
                if(j-w[i]>=0)
                {
                    dp[i][j]=max(dp[i-1][j], v[i]+dp[i-1][j-w[i]]);
                }
                else dp[i][j]=dp[i-1][j];

                if(dp[i][j]>mxfn || dp[i][j]==mxfn && mncst>j)
                {
                    mxfn=dp[i][j];
                    mncst=j;
                }
            }
        }
        cout<<mncst<< " "<<mxfn<<endl;
    }
    return 0;
}

##
In some problem, you have to make weight of TWO items in minimum possible cost.
There may be overflow in one weight, if another complete fast...So, to handle such situation,
we may write our recursive DP function as: :)

 p1=w[pos]+solve(pos+1, min(o,wt1+ar[pos]),min(n,wt2+br[pos]));
 p2=solve(pos+1,wt1,wt2);  

 ret=min(p1,p2);