Skip to Content
CTRL K

Money Sums

Análisis oficial (C++) 

Explicación

Para este problema, definimos dp[i][j]\texttt{dp[i][j]} como si es posible formar una suma de jj con ii monedas.

Y si recorremos todas las monedas y las sumas posibles, entonces obtenemos dos situaciones posibles:

Si es posible formar una suma de jj con menos de ii monedas, entonces formar la misma suma con más de ii monedas también será posible.

Y si es posible formar una suma de \texttt{current\\_sum - coin\\_value[i]} con i−1i - 1 monedas, entonces formar una suma de \texttt{current\\_sum} con ii monedas también será posible.

Y al final, podemos recorrer el arreglo dp\texttt{dp}, hallar todas las sums\texttt{sums} posibles con nn monedas, ponerlas en un arreglo dinámico, e imprimir el tamaño de ese arreglo dinámico y cada uno de sus elementos.

Implementación

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

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX_N = 100;
const int MAX_SUM = 1e5;
 
bool dp[MAX_N + 1][MAX_SUM + 1];
 
int main() {
	int n;
	cin >> n;
 
	vector<int> coins_values(n);
	for (int i = 0; i < n; i++) { cin >> coins_values[i]; }
 
	dp[0][0] = true;
 
	for (int i = 1; i <= n; i++) {
		for (int current_sum = 0; current_sum <= MAX_SUM; current_sum++) {
			dp[i][current_sum] = dp[i - 1][current_sum];
			int prev_sum = current_sum - coins_values[i - 1];
			if (prev_sum >= 0 && dp[i - 1][prev_sum]) { dp[i][current_sum] = true; }
		}
	}
 
	vector<int> possible;
	for (int sum = 1; sum <= MAX_SUM; sum++) {
		if (dp[n][sum]) { possible.push_back(sum); }
	}
 
	cout << (int)(possible.size()) << endl;
 
	for (int sum : possible) { cout << sum << " "; }
	cout << endl;
}
import java.io.*;
import java.util.*;
 
public class MoneySums {
	public static int maxSum = (int)1e5;
 
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio();
 
		int N = io.nextInt();
 
		int[] value = new int[N + 1];
		for (int i = 1; i <= N; i++) { value[i] = io.nextInt(); }
 
		boolean[][] dp = new boolean[N + 1][maxSum + 1];
 
		dp[0][0] = true;
 
		for (int i = 1; i <= N; i++) {
			for (int curSum = 0; curSum <= maxSum; curSum++) {
				dp[i][curSum] = dp[i - 1][curSum];
				int prevSum = curSum - value[i];
				if (prevSum >= 0 && dp[i - 1][prevSum]) { dp[i][curSum] = true; }
			}
		}
 
		ArrayList<Integer> possible = new ArrayList<>();
		for (int sum = 1; sum <= maxSum; sum++) {
			if (dp[N][sum]) { possible.add(sum); }
		}
		io.println(possible.size());
		for (int i : possible) { io.print(i + " "); }
		io.close();
	}
 
	// CodeSnip{Kattio}
}
n = int(input())
money = list(map(int, input().split()))
 
max_sum = n * 1000
dp = [[False] * (max_sum + 1) for _ in range(n + 1)]
dp[0][0] = True
 
for i in range(1, n + 1):
	for j in range(max_sum + 1):
		dp[i][j] = dp[i - 1][j]
		left = j - money[i - 1]
		if left >= 0 and dp[i - 1][left]:
			dp[i][j] = True
 
res = [i for i in range(1, max_sum + 1) if dp[n][i]]
 
print(len(res))
print(*res)
Fundamentos