Por qué la segunda versión de programación dinámica es incorrecta.
Si me dieran un conjunto de enteros positivos, como [2,19,6,16,5,10,7,4,11,6], quisiera encontrar el conjunto más grande que se puede obtener de ese conjunto anterior tal que la suma sea divisible por 3. Intento resolverlo usando programación dinámica.
Sea dp[i][j] el conjunto más grande alcanzado hasta el índice i en el conjunto con el resto de j, que es 0, 1, 2 ya que estoy buscando algo divisible por 3.
Y tengo dos implementaciones debajo:
int n = nums.length;
int[][] dp = new int[n+1][3];
dp[0][0] = 0;
dp[0][1] = Integer.MINVALUE;
dp[0][2] = Integer.MINVALUE;
for(int i = 1; i <= n; i++) {
for(int j = 0; j < 3; j++) {
int remain = nums[i-1] % 3;
int remainder = (j + 3 - remain) % 3;
dp[i][j] = Math.max(dp[i-1][remainder] + nums[i-1], dp[i-1][j]);
}
}
return dp[n][0];
int n = nums.length;
int[][] dp = new int[n+1][3];
dp[0][0] = nums[0] % 3 == 0 ? nums[0] : Integer.MIN_VALUE;
dp[0][1] = nums[0] % 3 == 1 ? nums[0] : Integer.MIN_VALUE;
dp[0][2] = nums[0] % 3 == 2 ? nums[0] : Integer.MIN_VALUE;
for(int i = 1; i < n; i++) {
for(int j = 0; j < 3; j++) {
int remain = nums[i] % 3;
int remainder = (j + 3 - remain) % 3;
dp[i][j] = Math.max(dp[i-1][remainder] + nums[i], dp[i-1][j]);
}
}
return dp[n-1][0] == Integer.MIN_VALUE ? 0 : dp[n-1][0];
Ambas implementaciones están basadas en el hecho de que agrego o no nums[i], y agrego nums[i] a la tabla con el resto correspondiente antes/después de agregar nums[i], que es como la programación dinámica de la mochila, pero la primera versión pasa todas las pruebas y la debajo falla para algunas de ellas. Como [2,19,6,16,5,10,7,4,11,6], da 81 en lugar de la respuesta correcta 84, ¿alguien puede explicar por qué la segunda versión es incorrecta?
davy.ai
La segunda versión del algoritmo de programación dinámica es incorrecta porque no tiene en cuenta la posibilidad de agregar varios elementos del array a la suma del subconjunto. En la primera versión, el algoritmo comprueba si el resto del elemento actual es igual al resto de la suma de los elementos ya agregados a la suma del subconjunto. Si es así, entonces el elemento actual se agrega a la suma del subconjunto. En la segunda versión, el algoritmo solo comprueba si el resto del elemento actual es igual al resto de la suma de los elementos ya agregados a la suma del subconjunto, pero no comprueba si se pueden agregar múltiples elementos a la suma del subconjunto. Esto significa que la segunda versión del algoritmo no podrá encontrar la solución óptima para el array dado.