Hay n personas y dos máquinas de votar idénticas. También se nos da una array a[] de tamaño n tal que a[i] almacena el tiempo requerido por la i-ésima persona para ir a cualquier máquina, marcar su voto y regresar. En un instante de tiempo, solo una persona puede estar allí en cada una de … Continue reading «Comprobar si todas las personas pueden votar en dos máquinas»
Dada una mochila con capacidad C y dos arrays w[] y val[] que representan los pesos y valores de N elementos distintos, la tarea es encontrar el valor máximo que puede poner en la mochila. Los artículos no se pueden romper y un artículo con peso X ocupa X capacidad de la mochila. Ejemplos: Entrada: … Continue reading «Mochila con Pesos grandes»
Dados los pesos y valores de N artículos y la capacidad W de la mochila. También dado que el peso de como máximo K elementos se puede cambiar a la mitad de su peso original. La tarea es encontrar la suma máxima de valores de N elementos que se pueden obtener de modo que la … Continue reading «Suma máxima de valores de N artículos en 0-1 Mochila al reducir el peso de como máximo K artículos a la mitad»
Dados los pesos y valores de n artículos, la tarea es poner estos artículos en una mochila de capacidad W para obtener el máximo valor total en la mochila, podemos poner repetidamente el mismo artículo y también podemos poner una fracción de un artículo. Ejemplos: Entrada: val[] = {14, 27, 44, 19}, wt[] = {6, … Continue reading «Mochila fraccional ilimitada»
Dados los pesos y valores de n artículos, coloque estos artículos en una mochila de capacidad W para obtener el valor total máximo en la mochila. En otras palabras, dadas dos arrays de enteros val[0..n-1] y wt[0..n-1] que representan valores y pesos asociados con n elementos respectivamente. También dado un número entero W que representa … Continue reading «0-1 Problema de mochila | DP-10 – Part 1»
Dados N elementos, cada uno de los cuales tiene un peso C i dado y un valor de beneficio P i , la tarea es maximizar el beneficio seleccionando un máximo de K elementos que sumen un peso máximo W . Ejemplos: Entrada: N = 5, P[] = {2, 7, 1, 5, 3}, C[] = … Continue reading «Problema de mochila extendida»
Branch andbound es un paradigma de diseño de algoritmos que generalmente se usa para resolver problemas de optimización combinatoria. Estos problemas suelen ser exponenciales en términos de complejidad de tiempo y pueden requerir explorar todas las permutaciones posibles en el peor de los casos. Branch and Bound resuelve estos problemas con relativa rapidez. Consideremos a … Continue reading «0/1 Mochila usando Rama y Atado»
¿Qué es un algoritmo pseudo-polinomio? Un algoritmo pseudo-polinomio es un algoritmo cuya complejidad temporal en el peor de los casos es polinomial en el valor numérico de la entrada (no en el número de entradas). Por ejemplo, considere el problema de contar las frecuencias de todos los elementos en una array de números positivos. Una solución … Continue reading «Algoritmos pseudo-polinomiales»
Dada una array arr[] , que consta de N enteros no negativos y un entero S , la tarea es encontrar el número de formas de obtener la suma S sumando o restando elementos de la array. Nota: Todos los elementos de la array deben participar en la generación de la suma. Ejemplos: Entrada: arr[] … Continue reading «Recuento de formas de obtener la suma dada a partir de los elementos de array dados»
Dada una array de enteros, que consiste en pesos positivos «W» y valores «V» respectivamente como un par y algunas consultas que consisten en un entero ‘C’ que especifica la capacidad de la mochila, encuentre el valor máximo de productos que se pueden poner en la mochila si se permite el rompimiento de objetos. Ejemplos: … Continue reading «Consultas fraccionarias de mochila»