Difícil · PD
Cambio de monedas
Este problema ya lo viste — con monedas 25/10/5/1, donde el voraz era demostrablemente óptimo. Cambia las denominaciones y esa prueba se evapora. La programación dinámica no mira qué monedas recibe: pregunta el mínimo honesto para cada subcantidad.
En una frase<code>best[0] = 0</code>; para cada cantidad x y moneda c: <code>best[x] = min(best[x], best[x-c] + 1)</code>. La respuesta es <code>best[amount]</code>, o -1 si nunca se hizo alcanzable.
El problema
Entrada: La primera línea trae n y amount (1 ≤ n ≤ 10, 1 ≤ amount ≤ 10000). La segunda, n denominaciones distintas (1 ≤ c ≤ 1000), con existencias ilimitadas de cada una.
Salida: Las mínimas monedas que suman exactamente amount, o -1 si es imposible.
Ejemplos:
| Entrada | Salida |
|---|---|
3 11 | 3 |
2 7 | -1 |
Con monedas {1, 3, 4} y cantidad 6, el voraz coge 4+1+1 (tres monedas) pero 3+3 bastan con dos — prueba ambos sobre las monedas del ejemplo y mira la diferencia. La tabla nunca elige la moneda localmente mejor; elige el mejor final.
Tu solución
Entrada personalizada para «Ejecutar mi entrada»
La corrección corre en tu navegador contra pruebas ocultas. Un bucle infinito se corta a los 3 segundos — aun así, asegúrate de que todo bucle tenga salida. Tu código se guarda solo mientras escribes.
¿Atascado? Pistas
Pista 1 — Define la celda antes del bucle
best[x] significa: las mínimas monedas que hacen exactamente x, o infinito si x es inalcanzable. Fijada la definición, la recurrencia casi se escribe sola — la última moneda de un pago óptimo de x es alguna c, y antes había un pago óptimo de x − c: best[x] = el mínimo de best[x-c] + 1.
Pista 2 — El infinito necesita guardaespaldas
Usa un INF grande (por ejemplo 1000000000) para las cantidades inalcanzables — pero resguarda la transición: if (best[x-c] != INF && best[x-c] + 1 < best[x]). Sin el resguardo, INF + 1 entra en la tabla y el veneno se propaga a todas las cantidades mayores. Ese chequeo ausente es el bug más común del problema.
Pista 3 — -1 también es una respuesta de la tabla
Tras el relleno, best[amount] contiene un conteo real o sigue siendo INF — en el segundo caso escribe -1. No intentes detectar la imposibilidad durante el bucle; la tabla está terminada cuando está terminada, y la imposibilidad es solo una celda que nunca mejoró.
Solución (¡inténtalo primero!)
#include <iostream>
using namespace std;
int best[10005];
int main() {
int n, amount;
cin >> n >> amount;
int c[10];
for (int i = 0; i < n; i++) cin >> c[i];
const int INF = 1000000000;
best[0] = 0;
for (int x = 1; x <= amount; x++) best[x] = INF;
for (int x = 1; x <= amount; x++) {
for (int i = 0; i < n; i++) {
if (c[i] <= x && best[x - c[i]] != INF && best[x - c[i]] + 1 < best[x]) {
best[x] = best[x - c[i]] + 1;
}
}
}
cout << (best[amount] == INF ? -1 : best[amount]) << endl;
return 0;
}Es la mochila ilimitada con su disfraz más simple, y la vindicación directa de Monedas mínimas — la misma historia, un capítulo después. El patrón a conservar: cuando el voraz no tiene prueba, define una tabla sobre subproblemas y deja que las transiciones decidan. La misma tabla con una dimensión más hace la mochila 0/1, luego subconjuntos, luego todo.
Análisis profundo
Por qué funciona
El voraz cogía la moneda mayor y fallaba con {1,3,4} — así que abandona las elecciones locales y define best[x] = mínimas monedas para exactamente x. La última moneda de cualquier pago óptimo es alguna c, luego best[x] = min(best[x−c] + 1) sobre las monedas. De abajo hacia arriba sobre x, cada subrespuesta está lista cuando se la referencia: no hace falta probar el voraz, porque no hay voraz.
El coste
O(n × amount) de tiempo, O(amount) de espacio — 10 × 10000 = 100.000 transiciones, instantáneo. La alternativa exponencial (probar cada moneda en cada paso) recalcula las mismas subcantidades un número astronómico de veces.
Dónde falla
- Dejar entrar INF+1 en la tabla: transicionar sin la guarda
best[x-c] != INFy el veneno se propaga a todas las cantidades mayores. Es el bug más común del problema, sin competencia. - Olvidar
best[0] = 0— el caso base que legaliza «pagar exactamente 0 con 0 monedas», de donde crecen todas las cadenas. - Escribir 0 en vez de -1 para cantidades imposibles, o detectar la imposibilidad dentro del bucle: la tabla se termina primero, la imposibilidad es solo una celda que sigue con INF.
Siguiente paso
La contraparte voraz que sí funciona (y por qué) es Monedas mínimas; la PD que escribiste aquí es la mochila ilimitada disfrazada. Con una dimensión más se vuelve la mochila 0/1 — la puerta a toda una familia.
Dos cosas para recordar
- Cuando el voraz no tiene prueba, define una tabla sobre subcantidades y deja que las transiciones decidan.
- INF es un centinela, no un número: resguarda toda transición que lo toque.
🐞 Esta versión falla: ábrela y pruébala
Voraz otra vez — para la cantidad 6 coge 4+1+1 donde 3+3 gasta dos
#include <iostream>
using namespace std;
int main() {
int n, amount;
cin >> n >> amount;
int c[10];
for (int i = 0; i < n; i++) cin >> c[i];
int left = amount, count = 0;
while (left > 0) {
int take = -1;
for (int i = 0; i < n; i++) {
if (c[i] <= left && c[i] > take) take = c[i]; // bug: greedy
}
if (take == -1) { cout << -1 << endl; return 0; }
left -= take;
count++;
}
cout << count << endl;
return 0;
}