Friki Work

La optimización de recursos bajo restricciones es un desafío recurrente en la informática y la ingeniería. Un ejemplo paradigmático de esto es el "Problema de la Mochila" (Knapsack Problem), donde el objetivo primordial es maximizar el valor total de un conjunto de objetos seleccionados para ser transportados en un contenedor con una ...

Se dispone de n (n ≤ 100) objetos y una mochila. El objeto i tiene un peso wi (wi ≤ 100) y un valor vi (vi ≤ 100). La capacidad de la mochila es C (C ≤ 1000). El objetivo es elegir los objetos que se introducen en la mochila para maximizar el valor total. Para cada objeto solo hay dos opciones: ponerlo o no ponerlo. No se puede introducir un ob ...

1. Fundamentos de la Monotonía de Decisión 1.1 Desigualdad de Cuadrilátero Se define una función de costo \(w(i, j)\) que satisface la desigualdad de cuadrilátero si para todo \(a \le b \le c \le d\), se cumple la siguiente relación: \[w(a, d) + w(b, c) \ge w(a, c) + w(b, d)\] Intuitivamente, esto significa que el costo de un intervalo que cont ...

Seleción de máximo un elemento por grupo Código de implementación #include <iostream> #include <algorithm> using namespace std; const int MAX = 1000; int dp[MAX][MAX]; int main() { int tipos, capacidad; cin >> tipos >> capacidad; for(int grupo = 1; grupo <= tipos; grupo++) { int elementos; ...

Modelo del Triángulo Numérico El problema del triángulo numérico consiste en encontrar la ruta de suma máxima (o mínima) desde la cima hasta la base de un triángulo de números, donde en cada paso solo se puede mover a los números adyacentes en la fila inferior. Este es un ejemplo introductorio clásico de la programación dinámica lineal. Enfoque ...

Este problema se enfoca en encontrar la distancia mínima en un grafo utilizando una técnica de "saltos" o "caminos acelerados", combinada con un algoritmo de ruta más corta entre todos los pares de nodos. La clave reside en la aplicación de la programación dinámica con un enfoque de exponenciación binaria (doubling) para con ...

Este documento presenta un análisis y solución para una serie de problemas de algoritmia, cubriendo conceptos como la teoría de grafos, cálculo de probabilidades con enfoques golosos y programación dinámica para la optimización de fracciones. Problema 1: Conjunto de Números Especiales Descripción General del Problema: Se define una función (f(x ...

Algoritmo 1: Pila La solución utiliza una pila para rastrear paréntesis no emparejados y sus posiciones. Al encontarr un paréntesis de cierre que coincide con el tope de la pila, se extrae el elemento y se calcula la longitud de la subcadena válida. Si la pila queda vacía tras la extracción, la subcadena abarca desde el inicio; de lo contrario, ...

Actualización continua... 1. Dos Números que Suman un Valor Objetivo Inicializar una tabla hash para almacenar los elementos del arreglo y sus índices. Recorrer el arrreglo; para cada elemento: Calcular la diferencia entre el valor objetivo y el elemento actual. Verificar si esta diferencia existe en la tabla hash. Si existe, se encontraron lo ...

La programación dinámica dinámica (DDP) es una extensión de la programación dinámica clásica que permite actualizar los estados de transición de manera eficiente durante la ejecución. La idea central es representar las transiciones de DP como matrices, lo que facilita su manipulación y consulta rápida usando estructuras de datos como árboles de ...