He interpretado el problema como encontrar el subconjunto con k o menos elementos de peso máximo menor que M. Parte de lo que describo a continuación es un poco complicado si necesita exactamente k elementos.
Hay una reducción obvia del problema de suma de subconjuntos a este problema, por lo tanto, está claro que este problema es NP completo. Los tres algoritmos descritos en la página de Wikipedia son aplicables aquí.
Si N es pequeño y M es grande, puede usar la técnica de división y combinación para obtener un algoritmo [matemático] O (N 2 ^ {\ frac {N} {2}}) [/ matemático].
- ¿Cuáles son las mejores estructuras de datos y algoritmos de entrenamiento en kolkata durante 2 meses?
- ¿Se puede usar la GPU para optimizar los algoritmos gráficos?
- ¿Cuál es la mejor manera de procesar consultas de accesibilidad en un DAG con restricciones?
- ¿Cómo se conocen entre sí los procesos en un sistema distribuido?
- Cómo probar la corrección del problema de cambio de moneda usando DP y poda
Si los elementos de su conjunto son todos enteros no negativos (o pueden transformarse para serlo) y NM tiene un tamaño manejable, puede usar una construcción de programación dinámica simple. Si [math] A_k [/ math] da el número mínimo de elementos necesarios para sumar a [math] k [/ math] (o infinito si es imposible), entonces podemos actualizar la matriz usando el elemento adicional [math] x [/ matemáticas] como:
[matemáticas] A’_k = min (A_k, 1 + A_ {kx}) [/ matemáticas]
Si ninguno de estos es cierto, es posible que deba recurrir a algoritmos de aproximación o búsqueda. El algoritmo de aproximación dado en la página Wiki, por ejemplo, puede permitirle encontrar la respuesta en tiempo polinómico siempre que la diferencia entre M y el tamaño máximo no sea una función insignificante.
