# Treasure and cities problem using dynamic programming | faceprep

Treasure and cities problem using dynamic programming is discussed here.

DESCRIPTION:

Given two arrays t and c denoting the treasure and color in each city. A city can be visited or skipped. You can only move forward. Whenever you visit a city you get the following amount.

1. a*t[i] if the color of the previously visited city is the same as the current city
2. b*t[i] if the color of the previously visited city is different from the current city or it is the first city to be visited.

Given that a, b, t[] can be negative and c[] varies from 1 to n.

Find the maximum money that can be earned by visiting each city.

Sample Input:
a = 5, b = -7
Array size = 4
Treasure array: {4, 8, 2, 9 }
Color array: { 2, 2, 3, 2 }

Sample Output:
Maximum profit: 57

Explanation:
Visit cities in the order 1 -> 2-> 4
Maximum profit = (-7 * 4) + (8 * 5) + (9 * 5) = 57

## Algorithm for treasure and cities problem

• Input the a and b values.
• Input the size of the treasure and color array.
• Input the treasure and color arrays.
• This problem is a variant of the 0-1 knapsack problem.
• Try all possible combinations to get the maximum cost and return the maximum cost.

Program for the treasure and cities problem is given below.

/* C++ program to solve the treasure and cities problem */

#include<bits/stdc++.h>
using namespace std;
int maxProfit(int t[],int c[],int n,int k,int col,int a,int b,int **dp)
{
if(k == n)
return 0;
if(dp[k][col] != -1)
return dp[k][col];
int sum;
if(col == c[k])
sum=max((a*t[k]+maxProfit(t,c,n,k+1,c[k],a,b,dp)),maxProfit(t,c,n,k+1,col,a,b,dp));
else
sum=max((b*t[k]+maxProfit(t,c,n,k+1,c[k],a,b,dp)),maxProfit(t,c,n,k+1,col,a,b,dp));
dp[k][col]=sum;
return dp[k][col];
}
int main()
{
int a,b;
cin>>a>>b;
int n;
cin>>n;
int t[n],c[n];
for(int i=0;i<n;i++)
cin>>t[i];
for(int i=0;i<n;i++)
cin>>c[i];
int **dp = (int **)malloc(n * sizeof(int *));
for (int i=0; i<n+1; i++)
dp[i] = (int *)malloc(n * sizeof(int));
for(int i=0;i<n;i++)
for(int j=0;j<n+1;j++)
dp[i][j]=-1;
cout<<maxProfit(t,c,n,0,0,a,b,dp);
}

Click edit button to change this text. Lorem ipsum dolor sit amet, consectetur adipiscing elit. Ut elit tellus, luctus nec ullamcorper mattis, pulvinar dapibus leo.

Test case 1

I/p
5 -7
4
4 8 2 9
2 2 3 2
O/P
57

Test Case 2

I/p
-5 7
4
4 8 2 9
2 2 3 2
O/P
133

Test Case 3

I/P
10 20
5
23 -45 -89 09 2
1 2 2 2 3
O/P
680

Test case 4

I/P
-98 -45
5
100 102 223 99 0
1 2 3 4 5
O/P
0

Test case 5

I/P
98 45
5
100 102 223 99 0
1 2 3 4 5
O/P
23580