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