Esta es la mejor solución que se me ocurre en este momento, puede haber una solución más rápida, pero no puedo pensar en ella en este momento.
Primero redefiniría el problema para tener copias [matemáticas] T [/ matemáticas] de cada una de las monedas [matemáticas] N [/ matemáticas]. Numere las monedas de [math] 1 [/ math] a [math] N \ cdot T [/ math], de modo que [math] val [i] [/ math] sea el valor de [math] i [/ math ] -th moneda.
Entonces deja
- ¿Cuál es el algoritmo de programación del juego para una temporada regular de la NBA?
- ¿Cómo se usaron los algoritmos cuando no había computadoras?
- ¿Qué algoritmos de Machine Learning pueden usarse para el aprendizaje supervisado incremental?
- ¿Qué canal / tutorial en YouTube es mejor para aprender algoritmos o estructuras de datos?
- ¿Cuáles son algunos de los algoritmos comunes y estrategias de diseño utilizados por los desarrolladores de juegos sin fin?
[matemáticas] formas [i] [j] [k] = [/ matemáticas] Número de formas en que podemos hacer un valor [matemáticas] j [/ matemáticas] si podemos usar monedas [matemáticas] 1, 2, \ ldots, i [ / math] y tenemos que tomar [math] k [/ math] monedas exactamente.
Para [matemática] 2 \ leq i \ leq N \ cdot T [/ matemática], [matemática] 1 \ leq j \ leq V [/ matemática], [matemática] 1 \ leq k \ leq K [/ matemática] [matemática ] [/matemáticas]
[matemáticas] formas [i] [j] [k] = formas [i-1] [j] [k] [/ matemáticas] (no tome monedas [matemáticas] i [/ matemáticas])
[matemática] + formas [i-1] [j – val [i]] [k-1] [/ matemática] if [matemática] j – val [i] \ geq 0 [/ matemática] (tomar moneda [matemática] i [/ matemáticas])
Para los casos base
- Hay una forma de hacer un valor de [matemáticas] 0 [/ matemáticas] sin monedas: no tomar nada
[matemática] formas [i] [0] [0] = 1 [/ matemática] para [matemática] 1 \ leq i \ leq N \ cdot T [/ matemática] - Con coin [math] 1 [/ math] solo podemos hacer [math] val [1] [/ math] con una moneda (o 0 sin monedas que está cubierto en el caso anterior)
[matemática] formas [1] [j] [k] = 1 [/ matemática] if [matemática] val [1] = j [/ matemática] y [matemática] k = 1 [/ matemática] más [matemática] 0 [ /matemáticas] - No hay forma de hacer un valor de [matemáticas] 0 [/ matemáticas] con una o más monedas
[matemáticas] formas [i] [0] [k] = 0 [/ matemáticas] para [matemáticas] 1 \ leq i \ leq N \ cdot T [/ matemáticas], [matemáticas] 1 \ leq k \ leq K [/ matemáticas]
Construir la tabla [matemáticas] formas [i] [j] [k] [/ matemáticas] lleva tiempo [matemáticas] O ([/ matemáticas] [matemáticas] N \ cdot T \ cdot V \ cdot K) [/ matemáticas] que puede ser bastante grande
Puede compararlo con la estrategia de recorrer todos los subconjuntos [matemática] K [/ matemática] de las monedas [matemática] N \ cdot T [/ matemática] que lleva tiempo [matemática] O (\ binom {N \ cdot T} {K}) [/ math] para decidir qué algoritmo es más rápido dependiendo de los parámetros.
