Given n cities: x1, x2, …… xn: each associated with T[i] (treasure) and C[i] (color). You can choose to visit a city or skip it. Only moving in the forward direction is allowed.When you visit a city you receive the following amount:
- A*T[i] if the color of visited city is the same as color of previously visited city
- B*T[i] if this is the first city visited or if the color of the visited city is different from the color of the previously visited city.The values of T[i], A and B can be negative while C[i] ranges from 1 to n.
We have to compute the maximum profit possible.
Examples:
Input : A = -5, B = 7
Treasure = {4, 8, 2, 9}
color = {2, 2, 3, 2}
Output : 133
Visit city 2, 3 and 4. Profit = 8*7+2*7+9*7 = 133
Input : A = 5, B = -7
Treasure = {4, 8, 2, 9}
color = {2, 2, 3, 2}
Output: 57
Visit city 1, 2, 4. Profit = (-7)*4+8*5+9*5 = 57
Source : Oracle Interview Experience Set 61.
This is a variation of standard 0/1 Knapsack problem. The idea is to either visit a city or skip it and return the maximum of both the cases.
Below is the solution of above problem.
C++
#include <bits/stdc++.h>using namespace std;// k is current index and col is previous color.int MaxProfit(int treasure[], int color[], int n, int k, int col, int A, int B){ int sum = 0; if (k == n) // base case return 0; // we have two options // either visit current city or skip that // check if color of this city is equal // to prev visited city if (col == color[k]) sum += max(A * treasure[k] + MaxProfit(treasure, color, n, k + 1, color[k], A, B), MaxProfit(treasure, color, n, k + 1, col, A, B)); else sum += max(B * treasure[k] + MaxProfit(treasure, color, n, k + 1, color[k], A, B), MaxProfit(treasure, color, n, k + 1, col, A, B)); // return max of both options return sum;}int main(){ int A = -5, B = 7; int treasure[] = { 4, 8, 2, 9 }; int color[] = { 2, 2, 6, 2 }; int n = sizeof(color) / sizeof(color[0]); // Initially begin with color 0 cout << MaxProfit(treasure, color, n, 0, 0, A, B); return 0;} |
Java
class GFG{ // k is current index and col is previous color. static int MaxProfit(int treasure[], int color[], int n, int k, int col, int A, int B) { int sum = 0; if (k == n) // base case return 0; // we have two options // either visit current city or skip that // check if color of this city is equal // to prev visited city if (col == color[k]) sum += Math.max(A * treasure[k] + MaxProfit(treasure, color, n, k + 1, color[k], A, B), MaxProfit(treasure, color, n, k + 1, col, A, B)); else sum += Math.max(B * treasure[k] + MaxProfit(treasure, color, n, k + 1, color[k], A, B), MaxProfit(treasure, color, n, k + 1, col, A, B)); // return max of both options return sum; } public static void main(String[] args) { int A = -5, B = 7; int treasure[] = { 4, 8, 2, 9 }; int color[] = { 2, 2, 6, 2 }; int n = color.length; // Initially begin with color 0 System.out.print(MaxProfit(treasure, color, n, 0, 0, A, B)); }} // This code is contributed by PrinciRaj1992 |
Python3
# k is current index and col# is previous color. def MaxProfit(treasure, color, n, k, col, A, B): sum = 0 if k == n: return 0 # we have two options either # visit current city or skip that # check if color of this city # is equal to prev visited city if col== color[k]: sum += max(A * treasure[k] + MaxProfit(treasure, color, n, k + 1, color[k], A, B), MaxProfit(treasure, color, n, k + 1, col, A, B)) else: sum += max(B * treasure[k] + MaxProfit(treasure, color, n, k + 1, color[k], A, B), MaxProfit(treasure, color, n, k + 1, col, A, B)) # return max of both options return sum# Driver CodeA = -5B= 7treasure = [4, 8, 2, 9]color = [2, 2, 6, 2]n = len(color)# Initially begin with color 0print( MaxProfit(treasure, color, n, 0, 0, A, B))# This code is contributed # by Shrikant13 |
C#
using System;class GFG{ // k is current index and col is previous color. static int MaxProfit(int []treasure, int []color, int n, int k, int col, int A, int B) { int sum = 0; if (k == n) // base case return 0; // we have two options // either visit current city or skip that // check if color of this city is equal // to prev visited city if (col == color[k]) sum += Math.Max(A * treasure[k] + MaxProfit(treasure, color, n, k + 1, color[k], A, B), MaxProfit(treasure, color, n, k + 1, col, A, B)); else sum += Math.Max(B * treasure[k] + MaxProfit(treasure, color, n, k + 1, color[k], A, B), MaxProfit(treasure, color, n, k + 1, col, A, B)); // return max of both options return sum; } // Driver codepublic static void Main(String[] args) { int A = -5, B = 7; int []treasure = { 4, 8, 2, 9 }; int []color = { 2, 2, 6, 2 }; int n = color.Length; // Initially begin with color 0 Console.Write(MaxProfit(treasure, color, n, 0, 0, A, B)); }} // This code is contributed by PrinciRaj1992 |
Javascript
<script>// k is current index and col is previous color.function MaxProfit(treasure,color,n,k,col,A,B){ let sum = 0; if (k == n) // base case return 0; // we have two options // either visit current city or skip that // check if color of this city is equal // to prev visited city if (col == color[k]) sum += Math.max(A * treasure[k] + MaxProfit(treasure, color, n, k + 1, color[k], A, B), MaxProfit(treasure, color, n, k + 1, col, A, B)); else sum += Math.max(B * treasure[k] + MaxProfit(treasure, color, n, k + 1, color[k], A, B), MaxProfit(treasure, color, n, k + 1, col, A, B)); // return max of both options return sum;}let A = -5, B = 7;let treasure = [ 4, 8, 2, 9 ];let color = [ 2, 2, 6, 2 ];let n = color.length;// Initially begin with color 0document.write(MaxProfit(treasure, color, n, 0, 0, A, B));// This code is contributed by rag2127</script> |
Output
133
Since subproblems are evaluated again, this problem has Overlapping Subproblems property.
Following is Dynamic Programming based implementation.
C++
// A memoization based program to find maximum// treasure that can be collected.#include <bits/stdc++.h>using namespace std;const int MAX = 1001;int dp[MAX][MAX];// k is current index and col is previous color.int MaxProfit(int treasure[], int color[], int n, int k, int col, int A, int B){ if (k == n) // base case return dp[k][col] = 0; if (dp[k][col] != -1) return dp[k][col]; int sum = 0; // we have two options // either visit current city or skip that if (col == color[k]) // check if color of this city is equal to prev visited city sum += max(A * treasure[k] + MaxProfit(treasure, color, n, k + 1, color[k], A, B), MaxProfit(treasure, color, n, k + 1, col, A, B)); else sum += max(B * treasure[k] + MaxProfit(treasure, color, n, k + 1, color[k], A, B), MaxProfit(treasure, color, n, k + 1, col, A, B)); // return max of both options return dp[k][col] = sum;}int main(){ int A = -5, B = 7; int treasure[] = { 4, 8, 2, 9 }; int color[] = { 2, 2, 6, 2 }; int n = sizeof(color) / sizeof(color[0]); memset(dp, -1, sizeof(dp)); cout << MaxProfit(treasure, color, n, 0, 0, A, B); return 0;} |
Java
// A memoization based program to find maximum// treasure that can be collected.import java.util.*;class GFG{static int MAX = 1001;static int [][]dp = new int[MAX][MAX];// k is current index and col is previous color.static int MaxProfit(int treasure[], int color[], int n, int k, int col, int A, int B){ if (k == n) // base case return dp[k][col] = 0; if (dp[k][col] != -1) return dp[k][col]; int sum = 0; // we have two options // either visit current city or skip that // check if color of this city // is equal to prev visited city if (col == color[k]) sum += Math.max(A * treasure[k] + MaxProfit(treasure, color, n, k + 1, color[k], A, B), MaxProfit(treasure, color, n, k + 1, col, A, B)); else sum += Math.max(B * treasure[k] + MaxProfit(treasure, color, n, k + 1, color[k], A, B), MaxProfit(treasure, color, n, k + 1, col, A, B)); // return max of both options return dp[k][col] = sum;}// Driver codepublic static void main(String[] args){ int A = -5, B = 7; int treasure[] = { 4, 8, 2, 9 }; int color[] = { 2, 2, 6, 2 }; int n = color.length; for (int i = 0; i < n; i++) for (int j = 0; j < MAX; j++) dp[i][j] = -1; System.out.print(MaxProfit(treasure, color, n, 0, 0, A, B));}}// This code is contributed by 29AjayKumar |
Python3
# A memoization based program to find maximum# treasure that can be collected.MAX = 1001dp = [[-1 for i in range(MAX)] for i in range(MAX)]# k is current index and col is previous color.def MaxProfit(treasure, color, n,k, col, A, B): if (k == n): # base case dp[k][col] = 0 return dp[k][col] if (dp[k][col] != -1): return dp[k][col] summ = 0 # we have two options # either visit current city or skip that if (col == color[k]): # check if color of this city is equal to prev visited city summ += max(A * treasure[k] + MaxProfit(treasure, color, n, k + 1,color[k], A, B), MaxProfit(treasure, color, n, k + 1, col, A, B)) else: summ += max(B * treasure[k] + MaxProfit(treasure, color, n, k + 1,color[k], A, B), MaxProfit(treasure, color, n, k + 1, col, A, B)) dp[k][col] = summ # return max of both options return dp[k][col]# Driver codeA = -5B = 7treasure = [ 4, 8, 2, 9 ]color = [ 2, 2, 6, 2 ]n = len(color)print(MaxProfit(treasure, color, n, 0, 0, A, B))# This code is contributed by shubhamsingh10 |
C#
// A memoization based program to find maximum// treasure that can be collected.using System;class GFG{ static int MAX = 1001; static int [,]dp = new int[MAX, MAX]; // k is current index and col is previous color.static int MaxProfit(int []treasure, int []color, int n, int k, int col, int A, int B){ if (k == n) // base case return dp[k, col] = 0; if (dp[k, col] != -1) return dp[k, col]; int sum = 0; // we have two options // either visit current city or skip that // check if color of this city // is equal to prev visited city if (col == color[k]) sum += Math.Max(A * treasure[k] + MaxProfit(treasure, color, n, k + 1, color[k], A, B), MaxProfit(treasure, color, n, k + 1, col, A, B)); else sum += Math.Max(B * treasure[k] + MaxProfit(treasure, color, n, k + 1, color[k], A, B), MaxProfit(treasure, color, n, k + 1, col, A, B)); // return max of both options return dp[k, col] = sum;} // Driver codepublic static void Main(String[] args){ int A = -5, B = 7; int []treasure = { 4, 8, 2, 9 }; int []color = { 2, 2, 6, 2 }; int n = color.Length; for (int i = 0; i < n; i++) for (int j = 0; j < MAX; j++) dp[i, j] = -1; Console.Write(MaxProfit(treasure, color, n, 0, 0, A, B));}}// This code is contributed by PrinciRaj1992 |
Javascript
<script>// A memoization based program to find maximum// treasure that can be collected.let MAX = 1001;let dp = new Array(MAX);for(let i = 0; i < MAX; i++){ dp[i] = new Array(MAX); for(let j = 0; j < MAX; j++) dp[i][j] = -1;}// k is current index and col is previous color.function MaxProfit(treasure, color, n, k, col, A, B){ if (k == n) // base case return dp[k][col] = 0; if (dp[k][col] != -1) return dp[k][col]; let sum = 0; // we have two options // either visit current city or skip that // check if color of this city // is equal to prev visited city if (col == color[k]) sum += Math.max(A * treasure[k] + MaxProfit(treasure, color, n, k + 1, color[k], A, B), MaxProfit(treasure, color, n, k + 1, col, A, B)); else sum += Math.max(B * treasure[k] + MaxProfit(treasure, color, n, k + 1, color[k], A, B), MaxProfit(treasure, color, n, k + 1, col, A, B)); // return max of both options return dp[k][col] = sum;}// Driver codelet A = -5, B = 7;let treasure=[4, 8, 2, 9];let color=[2, 2, 6, 2];let n = color.length;document.write(MaxProfit(treasure, color, n, 0, 0, A, B));// This code is contributed by avanitrachhadiya2155</script> |
Output
133
Efficient approach : Using DP Tabulation method ( Iterative approach )
The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memoization(top-down) because memoization method needs extra stack space of recursion calls.
Steps to solve this problem :
- Create a DP to store the solution of the subproblems and initialize it with 0.
- Initialize the DP with base cases
- Now Iterate over subproblems to get the value of current problem form previous computation of subproblems stored in DP.
- Return the final solution stored in dp[0][0].
Implementation :
C++
// A tabulation based program to find maximum// treasure that can be collected.#include <bits/stdc++.h>using namespace std;const int MAX = 1001;// k is current index and col is previous color.int MaxProfit(int treasure[], int color[], int n,int A, int B){ // to store computations int dp[n+1][MAX]; // initialize it with 0 memset(dp, 0, sizeof(dp)); // iteratively get the current // value from previous computations for(int i=n-1; i>=0; i--){ for(int j=0; j<MAX; j++){ // to store sum int sum = 0; // update sum in differnt conditions if(color[i] == j) sum += max(A*treasure[i]+dp[i+1][color[i]], dp[i+1][j]); else sum += max(B*treasure[i]+dp[i+1][color[i]], dp[i+1][j]); // update DP dp[i][j] = sum; } } // return answer return dp[0][0];}// Driver Codeint main(){ int A = -5, B = 7; int treasure[] = { 4, 8, 2, 9 }; int color[] = { 2, 2, 6, 2 }; int n = sizeof(color) / sizeof(color[0]); // function call cout << MaxProfit(treasure, color, n, A, B); return 0;} |
Java
import java.util.Arrays;public class TreasureHunter { private static final int MAX = 1001; public static int maxProfit(int[] treasure, int[] color, int n, int A, int B) { // to store computations int[][] dp = new int[n + 1][MAX]; // initialize it with 0 for (int i = 0; i <= n; i++) { Arrays.fill(dp[i], 0); } // iteratively get the current // value from previous computations for (int i = n - 1; i >= 0; i--) { for (int j = 0; j < MAX; j++) { // to store sum int sum = 0; // update sum in differnt conditions if (color[i] == j) { sum += Math.max( A * treasure[i] + dp[i + 1][color[i]], dp[i + 1][j]); } else { sum += Math.max( B * treasure[i] + dp[i + 1][color[i]], dp[i + 1][j]); } // update DP dp[i][j] = sum; } } // return answer return dp[0][0]; } // Driver Code public static void main(String[] args) { int A = -5, B = 7; int[] treasure = { 4, 8, 2, 9 }; int[] color = { 2, 2, 6, 2 }; int n = color.length; // function call System.out.println( maxProfit(treasure, color, n, A, B)); }} |
Python
# A tabulation based program to find maximum# treasure that can be collected.import sysMAX = 1001# k is current index and col is previous color.def MaxProfit(treasure, color, n, A, B): # to store computations dp = [[0 for j in range(MAX)] for i in range(n+1)] # iteratively get the current # value from previous computations for i in range(n-1, -1, -1): for j in range(MAX): # to store sum sum = 0 # update sum in differnt conditions if(color[i] == j): sum += max(A*treasure[i]+dp[i+1][color[i]], dp[i+1][j]) else: sum += max(B*treasure[i]+dp[i+1][color[i]], dp[i+1][j]) # update DP dp[i][j] = sum # return answer return dp[0][0]# Driver Codeif __name__ == "__main__": A = -5 B = 7 treasure = [4, 8, 2, 9] color = [2, 2, 6, 2] n = len(color) # function call print(MaxProfit(treasure, color, n, A, B)) |
C#
using System;class GFG{ const int MAX = 1001; // Function to find the maximum treasure that can be collected static int MaxProfit(int[] treasure, int[] color, int n, int A, int B) { // Create a DP array to store the computed values int[,] dp = new int[n + 1, MAX]; // Initialize the DP array with 0 for (int i = 0; i <= n; i++) { for (int j = 0; j < MAX; j++) { dp[i, j] = 0; } } // Iteratively calculate the maximum profit for (int i = n - 1; i >= 0; i--) { for (int j = 0; j < MAX; j++) { // Initialize the sum variable int sum = 0; // Update sum based on color match if (color[i] == j) { sum += Math.Max(A * treasure[i] + dp[i + 1, color[i]], dp[i + 1, j]); } else { sum += Math.Max(B * treasure[i] + dp[i + 1, color[i]], dp[i + 1, j]); } // Update the DP array dp[i, j] = sum; } } return dp[0, 0]; } // Driver Code static void Main() { int A = -5, B = 7; int[] treasure = { 4, 8, 2, 9 }; int[] color = { 2, 2, 6, 2 }; int n = color.Length; // Function call Console.WriteLine(MaxProfit(treasure, color, n, A, B)); }} |
Javascript
function MaxProfit(treasure, color, n, A, B) { const MAX = 1001; // Initialize a 2D array dp with zeros let dp = Array.from({ length: n + 1 }, () => Array(MAX).fill(0)); // Iteratively compute the maximum profit for (let i = n - 1; i >= 0; i--) { for (let j = 0; j < MAX; j++) { let sum = 0; // Update sum in different conditions if (color[i] === j) { sum += Math.max(A * treasure[i] + dp[i + 1][color[i]], dp[i + 1][j]); } else { sum += Math.max(B * treasure[i] + dp[i + 1][color[i]], dp[i + 1][j]); } // Update dp dp[i][j] = sum; } } // Return the answer return dp[0][0];}// Driver Codefunction main() { const A = -5; const B = 7; const treasure = [4, 8, 2, 9]; const color = [2, 2, 6, 2]; const n = color.length; // Function call console.log(MaxProfit(treasure, color, n, A, B));}main(); |
Output
133
Time Complexity: O(N*MAX)
Auxiliary Space: O(N*MAX)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
