0 like 0 dislike
1,240 views
| 1,240 views

0 like 0 dislike
Problem : there are n shops and each shop has n type of items. cost[i][j] is the cost of jth item type in ith shop. A person has to maximize expenditure. He can only buy 1 item from each shop and all purchased items should be of differnet types.
Input: cost[n][n] array
output: find max expenditure

Note: The selection should be such that each row and column are different .
by Expert (113,040 points)
0 like 0 dislike

``````#include<bits/stdc++.h>
using namespace std;

int soln(int i,int mask,int n,vector<vector<int>> cost,vector<vector<int>> &dp)
{
if(i==n)
return 0;

int ans=0;

for(int j=0;j<n;j++)
{
//check if item is already taken from another shop...
continue;

//if not taken take that item and set its mask...
}

}

int main()
{
int n;
cin>>n;
vector<vector<int>> cost(n,vector<int>(n));
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cin>>cost[i][j];
}
}

vector<vector<int>> dp(n+10,vector<int>(n+10,-1));

cout<<soln(0,0,n,cost,dp);
}``````
by Expert (113,040 points)
0 like 0 dislike
I think it can be solved by dynamic programming with bitmasking. here is the my code.

#include<bits/stdc++.h>
#define int long long
using namespace std;

int n;
vectordp;
vector<vector>cost;

{

if(idx==n)
{
return 0;
}

if(ans!=-1)return ans;
ans=0;

for(int col=0;col<n;col++)
{

int cur=n-col-1;
}

return ans;
}

int32_t main() {

cin>>n;
cost=vector<vector>(n,vector(n));
int N=1<<n+5;
dp=vector(N,-1);
for(int i=0;i<n;i++)for(int j=0;j<n;j++)cin>>cost[i][j];

int ans=solve(0,0);
cout<<ans;

}
by Expert (113,040 points)