Cómo resolver un problema de hacer cambios tomando como máximo una moneda de un tipo usando programación dinámica

Answer 1

Quora User, ¿cuál es la restricción del valor de n? es menos de 20?
si n alrededor de 20, entonces podemos usar (enmascaramiento de bits + dp) junto con la memorización para resolver el problema con dp [i] [j] donde i es la suma requerida para llegar a cero y j es la máscara de bits en la que se establecen todos los bits más para usar y los bits que no están establecidos ya se usan, por lo que dp [n] [2 ^ n] hará el trabajo.

Para la restricción n = 1000 alrededor
usaremos dos matrices, primero una matriz booleana (usada) un tamaño = suma acumulativa de todos los elementos de n suma vi donde 1 <= i <= n. y el conjunto usado [0] = verdadero, eso significa que la suma de cero es posible y dp [0] = 0, lo que significa que se requieren 0 monedas para obtener la suma como 0,
Luego, para cada elemento 1 <= i <= n, verificamos si del número de moneda con denominación vi podemos obtener una suma particular … entonces el código es el siguiente;
int dp [suma acumulativa];
bool utilizado [suma acumulativa];
memset (dp, INT_MAX, tamaño de dp);
memset (usado, falso, tamaño de usado);
dp [0] = 0;
utilizado [0] = falso;
para (int i = 0; i <n; i ++) {
para (int j = S; j> = 0; j -) {
if (usado [j]) {
utilizado [j + v [i]] = verdadero;
dp [j + v [i]] = min (dp [j + v [i]], dp [j] +1);
}
}
}
if (dp [S]! = INT_MAX)
cout << dp [S] << endl;
más
cout << "no es posible" <endl;

Espero que tengas la lógica detrás de eso 🙂

Answer 2

Esto se puede hacer de la misma manera que la mochila normal, pero con un cambio en el orden de iteración. Para cada moneda, repita los valores en orden descendente al actualizar la matriz en lugar de aumentar. Si esto se hace en orden descendente, obtenemos 0-1 mochila, donde cada elemento solo se puede usar una vez. De lo contrario, los valores dp se transferirán y tendremos una mochila normal.