Treasure and cities problem using dynamic programming | faceprep

Treasure and cities problem using dynamic programming | faceprep

Treasure and cities problem using dynamic programming is discussed here.

Treasure and cities problem using dynamic programming


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


faceprep pro ad bannerClick here to learn more about FACE Prep PRO


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

@@coding::1@@


Recommended Programs



Treasure and cities problem using dynamic programming