Dadas n ciudades: x1, x2, …… xn: cada una asociada con T[i] (tesoro) y C[i] (color). Puedes elegir visitar una ciudad u omitirla. Solo se permite moverse en la dirección de avance. Cuando visitas una ciudad, recibes la siguiente cantidad:
- A*T[i] si el color de la ciudad visitada es el mismo que el color de la ciudad visitada anteriormente
- B*T[i] si es la primera ciudad visitada o si el color de la ciudad visitada es diferente al color de la ciudad visitada anteriormente. Los valores de T[i], A y B pueden ser negativos mientras que C[i ] varía de 1 a n.
Tenemos que calcular el beneficio máximo posible.
Ejemplos:
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
Fuente : Oracle Interview Experience Set 61 .
Esta es una variación del problema estándar de la mochila 0/1 . La idea es visitar una ciudad o saltarla y devolver el máximo de ambos casos.
A continuación se muestra la solución del problema anterior.
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 Code A = -5 B= 7 treasure = [4, 8, 2, 9] color = [2, 2, 6, 2] n = len(color) # Initially begin with color 0 print( 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 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;
// 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 0
document.write(MaxProfit(treasure, color, n, 0, 0, A, B));
// This code is contributed by rag2127
</script>
Producción:
133
Dado que los subproblemas se evalúan nuevamente, este problema tiene la propiedad Superposición de subproblemas .
A continuación se muestra la implementación basada en la programación dinámica .
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 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;
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 = 1001 dp = [[-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 code A = -5 B = 7 treasure = [ 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 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;
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 code
let 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>
Producción:
133
Publicación traducida automáticamente
Artículo escrito por Kushdeep_Mittal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA