Asumo la siguiente estructura de su matriz de solución DP.
- 0/1 Mochila: las filas representan elementos y las columnas representan la capacidad general de la mochila.
- corte de varilla: las filas representan diferentes tamaños permitidos y las columnas representan la longitud total de la varilla.
En 0/1 Mochila, puede elegir un artículo como máximo una vez. Mientras que, en el corte de varillas, puede cortar una varilla en todos los tamaños permitidos varias veces (siempre que sea posible).
Esto significa que, en 0/1 Knapsack, para el subproblema donde decide elegir el elemento (si cabe en la capacidad), busca la solución óptima para la capacidad restante en la fila anterior (ya que no puede elige este artículo nuevamente).
- ¿Cuál es la complejidad temporal de las funciones incorporadas en C ++?
- ¿Qué es un árbol en el estudio de estructuras de datos y algoritmos?
- ¿Cuál es el mejor algoritmo para encontrar el número más pequeño (mínimo 40 dígitos) cuyo último dígito se mueve al frente y es nueve veces el número original?
- ¿Los algoritmos de aprendizaje automático han salido del laboratorio y han pasado a entornos clínicos que involucran pacientes?
- Cómo resolver el problema SPOJ XORROUND
Mientras que, en el corte de varilla, para el subproblema donde decide cortar la varilla en un tamaño particular (correspondiente a la fila), busca la solución opcional para la longitud restante en la misma fila (ya que puede cortar la varilla en la misma longitud varias veces).
En segundo lugar, realiza ajustes similares cuando recorre la matriz desde la última fila y la última columna para encontrar los elementos reales que dieron las soluciones óptimas en ambos problemas.
