Mi informacion de contacto
Correo[email protected]
2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
1、ecuación de transición de estado：
Entonces la fórmula recursiva: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - peso[i]] + valor[i]);
2. Inicialización
(1) A partir de la definición de dp [i] [j], si la capacidad de la mochila j es 0, es decir, dp [i] [0], no importa qué artículos se seleccionen, el valor total de la mochila debe ser 0.
(2) Ecuación de transición de estado dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - peso[i]] + valor[i]); visto que i se deriva de i-1, por lo que debe inicializarse cuando i es 0.
dp[0][j], es decir: i es 0, al almacenar el artículo número 0, el valor máximo que puede almacenar una mochila de cada capacidad.
Entonces es obvio que cuando j <peso[0], dp[0][j] debería ser 0, porque la capacidad de la mochila es menor que el peso del artículo numerado 0.
Cuando j >= peso[0], dp[0][j] debe ser el valor[0], porque la capacidad de la mochila es suficiente para contener el artículo número 0.
- for (int j = 0 ; j < weight[0]; j++) {
- dp[0][j] = 0;
- }
- // 正序遍历
- for (int j = weight[0]; j <= bagweight; j++) {
- dp[0][j] = value[0];
- }
(3) Otra inicialización de subíndice:
dp[i][j] = máx(dp[i - 1][j], dp[i - 1][j - peso[i]] + valor[i])
dp[1][1] = max(dp[0][1], dp[0][1- peso[i]] + valor[i]) debe estar a la izquierda y encima de él,
Por lo tanto, debe haberse inicializado y se puede establecer en cualquier valor. Por conveniencia, se inicializa en 0 de forma predeterminada.
2. Unidimensional (matriz rodante)
1. En la matriz dp unidimensional, dp[j] significa: una mochila con una capacidad de j puede transportar artículos con un valor máximo de dp[j]
dp[j] = max(dp[j], dp[j - weight[i]] + value[i])2. Inicialización
(1) dp[0]=0, porque el valor máximo de artículos que lleva una mochila con capacidad 0 es 0.
(2) Suponga que el valor de los artículos es mayor que 0,Para no ser sobrescrito por el valor inicial, entonces dpInicialización de matrizCuando, inicialmente todos son 0
3. Orden transversal
Atravesar en orden inverso
Explicación 1: El valor al final de la lista debe determinarse comparándolo con el valor anterior obtenido al atravesar el nivel anterior.
Explicación 2: Solo hay una mochila 01 para cada mochila. El hecho de que esta bolsa se coloque o no está relacionado con el estado de la bolsa anterior. La matriz de la izquierda es una cantidad que describe el estado de la bolsa anterior y el número. el de la derecha es un estado pendiente de la bolsa actual. En el código, el número de la izquierda es necesario para determinar la matriz de la derecha, por lo que el número de la izquierda no se puede destruir antes de que se calcule el número de la derecha.
Explicación 3: Para dos dimensiones, los resultados de cada uno de mis nuevos números dp provienen de arriba y de izquierda, de hecho, este debería ser el caso en una dimensión, pero en una dimensión, si todavía es de izquierda a derecha, entonces; mi izquierda real Las cifras han sido actualizadas ( ¡El lado izquierdo ya no es el lado izquierdo “original”!Esto provocará una doble contabilización. ), incluso si la tapa sigue siendo la tapa original, el número obtenido es incorrecto.Y si recorremos de derecha a izquierda en la capa de mochila (capa interior), entonces el elemento de la izquierda siempre seráNo se sobrescribirá con nuevos valores debido a mi operación anterior., para que se pueda obtener el valor correcto.
3. Solicitud
1. Dada una matriz no vacía que contiene solo números enteros positivos. ¿Es posible dividir esta matriz en dos subconjuntos de modo que la suma de los elementos de los dos subconjuntos sea igual?
Nota: Los elementos de cada matriz no excederán 100 y el tamaño de la matriz no excederá 200
Ejemplo 1:
analizar:
El artículo soy yo,
El peso es nums[i], el valor también es nums[i] y el volumen de la mochila es sum/2.
Similar a 01 mochila
Ecuación de transición de estado:
dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])- // 开始 01背包
- for(int i = 0; i < nums.size(); i++) {
- for(int j = target; j >= nums[i]; j--) {
- dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
- }
- }
- // 集合中的元素正好可以凑成总和target
- if (dp[target] == target) return true;
2. Hay un montón de piedras y el peso de cada piedra es un número entero positivo.
En cada ronda, elige dos rocas cualesquiera y aplastalas. Supongamos que los pesos de las piedras son x e y, y x <= y. Entonces los posibles resultados de la trituración son los siguientes:
Si x == y, entonces ambas rocas quedarán completamente aplastadas;
Si x != y, entonces la piedra de peso x se romperá por completo y la piedra de peso y tendrá un nuevo peso de yx.
Al final, como mucho sólo quedará una piedra. Devuelve el menor peso posible de esta piedra. Si no quedan piedras, se devuelve 0.
Ejemplo:
analizar:
Intente dividir las piedras en dos montones del mismo peso, de modo que la piedra más pequeña que quede después de la colisión
Luego divídalo en dos montones de piedras. El peso total de un montón de piedras es dp [objetivo] y el peso total del otro montón es dp [objetivo].
Al calcular el objetivo, objetivo = suma / 2 porque se redondea hacia abajo, por lo que suma - dp[objetivo] debe ser mayor o igual que dp[objetivo]
Entonces el peso mínimo de la piedra que queda después de la colisión es (suma - dp[objetivo]) - dp[objetivo]
- for (int i = 0; i < stones.length; i++) {
- //采用倒序
- for (int j = target; j >= stones[i]; j--) {
- dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
- }
- }
- //结果
- sum - 2 * dp[target];
citado de:Notas aleatorias de código
Se ha dedicado a la investigación de tecnología durante más de 30 años y domina varios lenguajes como java, linux, javascript, php, css, etc. Ha realizado muchas contribuciones en el campo del código abierto. Estación de documentación para desarrolladores para compartir algunos problemas en el desarrollo de tecnología para referencia futura.
Correo[email protected]