[go: up one dir, main page]
Scribd
Upload
70 views3 pages

Bitmask DP

Uploaded by

musannanafis
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
70 views3 pages

Bitmask DP

Uploaded by

musannanafis
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
You are on page 1/ 3

1)

Problem Statement

Let there be N workers and N jobs. Any worker can be assigned to perform any job,
incurring some cost that may vary depending on the work-job assignment. It is
required to perform all jobs by assigning exactly one worker to each job and
exactly one job to each agent in such a way that the total cost of the assignment
is minimized.

Input Format
Number of workers and job: N
Cost matrix C with dimension N*N where C(i,j) is the cost incurred on assigning ith
Person to jth Job.

Sample Input
4

[
9 2 7 8
6 4 3 7
5 8 1 8
7 6 9 4
]

Sample Output
13

Constraints
N <= 20

/////////////////////////////////////////////////////////

CODE:

#include<bits/stdc++.h>
typedef long long int ll;
typedef long int l;
typedef long double ld;

#define endl "\n"


#define BOOST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) ((a*b)/(gcd(a,b)))
#define pow(a, b) (ll)(pow(a,b)+1e-9)
#define vsorti(v) sort(v.begin(),v.end())
#define vsortd(v) sort(v.begin(), v.end(), greater<ll>());
#define asorti(a,n) sort(a+1,a+1+n);
#define asortd(a,n) sort(a+1,a+1+n, greater<ll>());

#define fo(n) for(int i=1;i<=n;i++)


#define fo1(n) for(int i=0;i<n;i++)
#define fov(v) for(int i=0;i<v.size();i++)
#define fos(s) for(int i=0;i<s.size();i++)

using namespace std;

/*
bool cmp ( pii A , pii B)
{
return A.first < B.first;
}
struct structure_name
{
int u,v,w;
structure_name(int _u,int _v,int _w)
{
u=_u;
v=_v;
w=_w;
}
};
*/
////////////////CODE/////////////////////////////////

ll dp[22][1<<21];
ll a[22][22];
ll n;
ll mydp(ll posi,ll mask)
{
if(posi>=n) return 0;
if(dp[posi][mask]!=-1) return dp[posi][mask];
ll ans=intmax;
for(int i=0;i<n;i++)
{
if((1<<i)&mask)
{

}
else
{
ans=min(ans,mydp(posi+1,((1<<i)|mask))+a[posi][i]);
}
}
return dp[posi][mask]=ans;
}
void solve()
{

cin>>n;
fo1(n)
{
for(int j=0;j<n;j++)
{
cin>>a[i][j];
}
}

cout<<mydp(0,0)<<endl;

int main()
{

BOOST;
//READ("in.txt");
//WRITE("out.txt");

int q;
cin>>q;
fo(q)
{
mem(dp,-1);
solve();
}

return 0;
}

//////////END//////////////////

Problems:
1) https://www.hackerrank.com/contests/phitron-programming-contest-2022/
challenges/chinki-and-minki

You might also like