DP de mochila (Knapsack)

Tutorial

Los problemas de mochila (knapsack) suelen consistir en llenar un recipiente limitado con un subconjunto de ítems, de modo que se cuente u optimice alguna cantidad asociada a esos ítems. Casi siempre se puede pensar que cada ítem tiene un peso positivo, y que el peso total de los ítems que elijamos no puede exceder la capacidad del recipiente, que es un número. Algunas variantes de problemas tipo mochila son:

• El problema de la mochila 0/1 : elegir un subconjunto de ítems que maximice el valor total sin que el peso total exceda la capacidad del recipiente
• Hallar todos los pesos totales posibles que se pueden alcanzar con cualquier subconjunto de ítems cuyo peso total no exceda la capacidad del recipiente (en el capítulo de CPH enlazado arriba)
• Contar cuántas secuencias de ítems llenan el recipiente por completo, es decir, que el peso total sea exactamente la capacidad del recipiente (el orden puede o no importar)

La solución de DP de los problemas de mochila suele tener un estado que registra la capacidad de la mochila, y las transiciones consisten en intentar agregar un ítem. En programación competitiva es de esperar que los problemas clásicos de mochila vengan con giros, disfraces e información extra en el estado.

Solución - Dice Combinations

Complejidad temporal: $\mathcal{O}(N)$

El problema pide cuántas secuencias de tiradas de dado existen tales que la suma de las caras superiores sea $N$ ($N \leq 10^6$). Siguiendo la analogía de la mochila, tenemos infinitos ítems de pesos $1$ a $6$, y queremos contar cuántas secuencias de ítems existen de modo que, si los ponemos en el recipiente siguiendo la secuencia, el recipiente quede completamente lleno. Nótese que en este problema el orden de los ítems importa.

Por comodidad, sea $\texttt{dp}[x]$ la cantidad de secuencias de tiradas de dado que suman $x$. Para contar cuántas secuencias suman $N$, o sea, para hallar $\texttt{dp}[N]$, miremos la última tirada que nos lleva a una suma total de $N$.

Si la última tirada fue un $1$, hay $\texttt{dp}[N-1]$ formas de alcanzar la suma $N$ cuando la última tirada es $1$. Si la última tirada fue un $2$, hay $\texttt{dp}[N-2]$ formas de alcanzar la suma $N$ cuando la última tirada es $2$. Continuamos esta lógica para todos los números del dado hasta $6$. Considerando todos esos casos juntos, queda demostrado que

Aplicamos la misma lógica que usamos para $\texttt{dp}[N]$ a un $x$ general:

Empezamos con el caso base $\texttt{dp}[0] = 1$, y después $\texttt{dp}[1]$, $\texttt{dp}[2]$, $\texttt{dp}[3]$, y así sucesivamente… se pueden calcular con la recurrencia hasta hallar $\texttt{dp}[N]$. Nótese en el código que ignoramos $\texttt{dp}[x]$ si $x < 0$.

#include <bits/stdc++.h>
 
using namespace std;
 
long long dp[1000001];
 
int main() {
	int n;
	cin >> n;
	dp[0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= 6; j++) {
			if (i - j >= 0) { dp[i] += dp[i - j]; }
		}
		dp[i] %= 1000000007;
	}
	cout << dp[n] << "\n";
}

 
import java.io.*;
import java.util.*;
 
public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n;
		n = Integer.parseInt(br.readLine());
 
		long dp[] = new long[n + 1];
		dp[0] = 1;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= 6; j++) {
				if (i - j >= 0) { dp[i] += dp[i - j]; }
			}
			dp[i] %= 1000000007;
		}
 
		System.out.println(dp[n]);
	}
}

dp = [1]
for i in range(int(input())):
	dp.append(sum(dp[-6:]) % (10**9 + 7))
print(dp[-1])

Problemas

Generales

USACO

Teoría de números

¡Algunos problemas de mochila con giros de teoría de números!