Skip to Content
CTRL K

Minimizing Coins

Explicación

En este problema, se nos pide el número mínimo de monedas de pesos distintos necesarias para alcanzar cierto peso, xx. Se puede leer sobre la solución de este problema clásico en CPH Capítulo 7 bajo “Coin Problem”.

Para este problema, definiremos dp[w]\texttt{dp[w]} como el número mínimo de monedas para alcanzar cierto peso ww. Luego, en algún ww, podemos intentar usar cada moneda. Usar la ii-ésima moneda representa transicionar desde el estado dp[w - coins[i]]\texttt{dp[w - coins[i]]}, donde coins[i]\texttt{coins[i]} representa el valor de la ii-ésima moneda. Así, para dp[i]\texttt{dp[i]}, la transición es:

dp[w]=min⁡i=1n(dp[w−coins[i]])+1 dp[w] = \min_{i=1}^n{(dp[w - coins[i]]) + 1}

Finalmente, el caso base sería dp[0]=0\texttt{dp[0]} = 0, ya que se requieren 00 monedas para obtener una suma de 00.

Implementación

Complejidad temporal: O(N⋅X)\mathcal O(N\cdot X)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
ll dp[1000001];
 
const int MOD = 1e9 + 7;
 
int main() {
	int n, x;
	cin >> n >> x;
	vector<int> coins(n);
	for (int i = 0; i < n; i++) { cin >> coins[i]; }
 
	for (int i = 0; i <= x; i++) { dp[i] = INT_MAX; }
	dp[0] = 0;
	for (int i = 1; i <= n; i++) {
		for (int weight = coins[i - 1]; weight <= x; weight++) {
			dp[weight] = min(dp[weight], dp[weight - coins[i - 1]] + 1);
		}
	}
 
	cout << (dp[x] == INT_MAX ? -1 : dp[x]) << endl;
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class MinCoins {
	public static int MAX = (int)10e6 + 2;
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int X = Integer.parseInt(st.nextToken());
 
		/* Leer los pesos de las monedas. */
		int[] coins = new int[N];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) { coins[i] = Integer.parseInt(st.nextToken()); }
 
		/* Inicializar DP. */
		int[] dp = new int[X + 1];
		for (int i = 0; i <= X; i++) { dp[i] = MAX; }
		dp[0] = 0;
 
		/* Recorrer todas las monedas y todos los pesos
		Si el estado curWeight - coin[i] es posible
		DP[curWeight] = min(DP[curWeight], DP[curWeight - coin[i]] + 1). */
		for (int i = 1; i <= N; i++) {
			for (int sum = coins[i - 1]; sum <= X; sum++) {
				dp[sum] = Integer.min(dp[sum], dp[sum - coins[i - 1]] + 1);
			}
		}
 
		/* Este estado no es posible */
		if (dp[X] == MAX) {
			System.out.println(-1);
			System.exit(0);
		}
 
		System.out.println(dp[X]);
	}
}
INF = 1000000000  # Usar float('inf') resulta en TLE
 
n, x = map(int, input().split())
c = list(map(int, input().split()))
 
dp = [INF] * (x + 1)
dp[0] = 0  # Caso base: se necesitan 0 monedas para una suma de 0
 
for coin in c:
	for i in range(x - coin + 1):
		"""
		Transición de DP: el estado i necesita dp[i] monedas,
		así que el estado i + coin se puede formar con dp[i] + 1 monedas.
		"""
		dp[i + coin] = min(dp[i + coin], dp[i] + 1)
 
 
print(dp[x] if dp[x] != INF else -1)
Fundamentos