Es fácil formular el DP cuando puede pensar de forma recursiva.
Intentemos definir un estado DP como [math] dp (i, diff, pos) [/ math] que denota el factor de injusticia de una distribución considerando los primeros i enteros de la secuencia dada.
- El parámetro [math] i [/ math] denota la longitud actual de la secuencia recorrida.
- El parámetro [math] diff [/ math] denota la diferencia absoluta actual entre la suma de monedas que tiene cada persona después de que se decide la distribución de [math] x_ {i} [/ math] coin.
- El parámetro [math] pos [/ math] indica si el [math] diff [/ math] obtenido hasta ahora es positivo o negativo, es decir, la suma de monedas es mayor para la primera persona o la segunda persona. ( ¿Por qué necesita almacenar esto? Porque no puede almacenar un argumento negativo en el estado y continuar almacenándolo en caché ya que la matriz no puede tener índices negativos ).
Ahora, veremos cómo se realiza la transición de un estado a otro. Más formalmente, intentaremos escribir ecuaciones que nos ayudarán a calcular la respuesta para el siguiente estado utilizando los valores calculados a partir del estado anterior.
- Cómo usar lower_bound para buscar una cadena en una estructura vectorial
- ¿Debo comenzar a aprender algoritmos y estructura de datos si solo tengo algunos conocimientos básicos de programación Java?
- ¿Dónde debo desarrollar mi lógica, en matemáticas relacionadas con la programación?
- ¿Por qué los temas 'estructura de datos' y 'algoritmo' siempre están conectados? ¿Hay un curso o libro que solo se ocupe de la estructura de datos?
- ¿Qué algoritmos se usan para calcular logaritmos?
- Bueno, no tengo ningún estado anterior para calcular mi respuesta cuando se decide la distribución de la primera moneda. Pero, de todos modos, puedo inicializar mi matriz DP para la moneda inicial. Este es también mi caso base del DP.
- [matemática] dp (0, moneda [0], 1) = moneda [0] [/ matemática]
- [matemática] dp (0, moneda [0], 0) = moneda [0] [/ matemática]
- Para las monedas que no sean la primera moneda, calculamos las respuestas de los estados anteriores.
- [matemática] dp (i, diff, 1) = min (dp (i, diff, 1), max (diff, dp (i – 1, abs (diff – moneda [i]), (diff – moneda [i] )> = 0))) [/ math]
- [matemática] dp (i, diff, 1) = min (dp (i, diff, 1), max (diff, dp (i – 1, diff + coin [i], 1))) [/ math]
- [matemática] dp (i, diff, 0) = min (dp (i, diff, 0), max (diff, dp (i – 1, abs (moneda [i] – diff), (moneda [i] – diff )> = 0))) [/ math]
- [matemática] dp (i, diff, 0) = min (dp (i, diff, 0), max (diff, dp (i – 1, diff + coin [i], 0))) [/ math]
Ahora, ¿cómo son válidas las ecuaciones anteriores? Mantener esto como un ejercicio para el lector. Para los detalles de implementación, eche un vistazo al siguiente código.
Enfoque de arriba hacia abajo
#include
#define MAX 102
#define INF 1000000000
usando el espacio de nombres estándar;
int A [MAX];
int n;
int tc;
int vis [101] [10001] [2];
int dp [101] [10001] [2];
int f (int idx, int diff, int neg)
{
if (idx == n) devuelve diff;
if (vis [idx] [diff] [neg] == tc) devuelve dp [idx] [diff] [neg];
vis [idx] [diff] [neg] = tc;
int ac_diff = diff;
if (neg) ac_diff * = -1;
int ans = INF;
ans = min (ans, max (diff, f (idx + 1, abs (ac_diff + A [idx]), (ac_diff + A [idx]) <0)));
ans = min (ans, max (diff, f (idx + 1, abs (ac_diff – A [idx]), (ac_diff – A [idx]) <0)));
dp [idx] [diff] [neg] = ans;
volver ans;
}
int main ()
{
int t;
scanf (“% d”, & t);
para (tc = 1; tc <= t; tc ++) {
scanf (“% d”, & n);
para (int i = 0; i <n; i ++) scanf ("% d", & A [i]);
printf (“% d \ n”, f (0, 0, 0));
}
devuelve 0;
}
Enfoque de abajo hacia arriba
#include
#define MAX 102
#define INF 1000000000
usando el espacio de nombres estándar;
int coin [MAX];
int dp [MAX] [MAX * MAX] [2];
int main ()
{
int t, n, suma;
cin >> t;
mientras que (t–) {
suma = 0;
cin >> n;
para (int i = 0; i <n; i ++) {
cin >> moneda [i];
suma + = moneda [i];
}
para (int i = 0; i <n; i ++) {
para (int j = 0; j <= sum; j ++) {
para (int k = 0; k <2; k ++) dp [i] [j] [k] = INF;
}
}
dp [0] [moneda [0]] [0] = dp [0] [moneda [0]] [1] = moneda [0];
para (int i = 1; i <n; i ++) {
para (int j = 0; j <= sum; j ++) {
if (dp [i – 1] [abs (j – moneda [i])] [(j – moneda [i])> = 0]! = INF) {
dp [i] [j] [1] = min (dp [i] [j] [1], max (j, dp [i – 1] [abs (j – moneda [i])] [(j – moneda [i])> = 0]));
}
if (j + coin [i] <= sum && dp [i – 1] [j + coin [i]] [1]! = INF) {
dp [i] [j] [1] = min (dp [i] [j] [1], max (j, dp [i – 1] [j + moneda [i]] [1]));
}
if (dp [i – 1] [abs (moneda [i] – j)] [(moneda [i] – j)> = 0]! = INF) {
dp [i] [j] [0] = min (dp [i] [j] [0], max (j, dp [i – 1] [abs (moneda [i] – j)] [(moneda [i ] – j)> = 0]));
}
if (j + coin [i] <= sum && dp [i – 1] [j + coin [i]] [0]! = INF) {
dp [i] [j] [0] = min (dp [i] [j] [0], max (j, dp [i – 1] [j + moneda [i]] [0]));
}
}
}
int ans = INF;
for (int j = 0; j <= sum; j ++) ans = min (ans, min (dp [n – 1] [j] [1], dp [n – 1] [j] [0]));
cout << ans << endl;
}
devuelve 0;
}
Si le gustó mi respuesta, es posible que le guste mi blog detallado sobre Programación dinámica que cubre los conceptos básicos de DP utilizando enfoques ascendentes y descendentes.
