Question

De shaw DP problem Online Campus placement | Set-26 | 2022

Answer 1

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 .

Answer 2

 solution of DP with bitmasks...

 

#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;
    if(dp[i][mask]!=-1)
        return dp[i][mask];
    
    int ans=0;
    
    for(int j=0;j<n;j++)
    {
        //check if item is already taken from another shop...
        if(mask & (1<<j))
            continue;
            
        //if not taken take that item and set its mask...
        ans=max(ans , cost[i][j]+soln(i+1,mask|(1<<j),n,cost,dp));
    }
    
    return dp[i][mask]=ans;
}

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);
}

Answer 3

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;

int solve(int idx,int mask)
{

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

int& ans=dp[mask];
if(ans!=-1)return ans;
ans=0;

for(int col=0;col<n;col++)
{
    
    int cur=n-col-1;
    if(mask & (1<<cur))continue;
    ans=max(ans,cost[idx][col]+solve(idx+1,mask|(1<<cur)));    
}

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;

}