Book Shop

Explicación

Para cada libro $i$ , o lo compramos, gastando $h[i]$ para ganar $s[i]$ páginas, o lo saltamos y no ganamos nada. Este es el problema de la mochila 0/1, con costo $h[i]$ , valor $s[i]$ y capacidad $x$ , lo que permite una solución de DP.

Sea $dp[i][j]$ el número máximo de páginas obtenible usando solo los primeros $i$ libros con un presupuesto de a lo sumo $j$ . El caso base es $dp[0][j] = 0$ para todo $j$ , ya que sin libros disponibles no se pueden obtener páginas, independientemente del presupuesto.

La transición queda así:

$dp[i][j] = dp[i-1][j]$ por defecto (saltar el libro $i$ )
si $j \geq h[i]$ , en su lugar podemos comprar el libro $i$ , dando $dp[i][j] = \max(dp[i-1][j], dp[i-1][j-h[i]] + s[i])$

La respuesta final es $dp[n][x]$ .

Mochila 1D

Como $dp[i][j]$ solo depende de la fila $i-1$ , no hace falta conservar todas las filas: podemos comprimir la DP en un solo arreglo 1D de tamaño $x+1$ , sobrescribiéndolo in situ a medida que avanzamos. Para cada libro $i$ , iteramos $j$ de $x$ hacia abajo hasta $h[i]$ , actualizando $dp[j] = \max(dp[j], dp[j-h[i]] + s[i])$ . Ir hacia abajo importa: mantiene $dp[j-h[i]]$ con el valor del libro anterior (fila $i-1$ ) cuando lo leemos, en vez de un valor ya actualizado para el libro $i$ (lo que nos permitiría comprar el mismo libro dos veces).

Implementación

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

C++Java


#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int n;
	int x;
	cin >> n >> x;
	vector<int> cost(n);
	vector<int> pages(n);
 
	for (int i = 0; i < n; i++) { cin >> cost[i]; }
	for (int i = 0; i < n; i++) { cin >> pages[i]; }
 
	/*
	 * dp[i][j] es el mayor número de páginas que se pueden comprar de
	 * los primeros i libros gastando a lo sumo j de dinero.
	 */
	vector<vector<int>> dp(n + 1, vector<int>(x + 1));
	for (int i = 1; i <= n; i++) {
		int curr_cost = cost[i - 1];
		int curr_pages = pages[i - 1];
		for (int j = 1; j <= x; j++) {
			/*
			 * si no se compra el libro actual, el número de páginas es
			 * el mismo que el número de páginas compradas con los primeros i-1 libros
			 * usando j de dinero
			 */
			dp[i][j] = dp[i - 1][j];
			if (curr_cost <= j) {
				/*
				 * si se puede comprar el libro actual, entonces guardar el mayor
				 * número de páginas usando el dinero restante después de comprar
				 * el libro actual más las páginas del libro actual.
				 */
				dp[i][j] = max(dp[i][j], dp[i - 1][j - curr_cost] + curr_pages);
			}
		}
	}
	cout << dp[n][x] << '\n';
}


import java.io.*;
import java.util.*;
 
public class bookShop {
	public static void main(String[] args) throws IOException {
		BufferedReader b = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(b.readLine());
		int N = Integer.parseInt(st.nextToken());
		int X = Integer.parseInt(st.nextToken());
 
		// Leer el arreglo de costos.
		int[] costs = new int[N];
		st = new StringTokenizer(b.readLine());
		for (int i = 0; i < N; i++) { costs[i] = Integer.parseInt(st.nextToken()); }
 
		// Leer el arreglo de páginas.
		int[] pages = new int[N];
		st = new StringTokenizer(b.readLine());
		for (int i = 0; i < N; i++) { pages[i] = Integer.parseInt(st.nextToken()); }
 
		// dp[i][j] es cuántas páginas tienes de los primeros i libros,
		// después de gastar j de dinero.
		int[][] dp = new int[N + 5][X + 5];
		for (int book = 0; book < N; book++) {
			for (int money = 0; money <= X; money++) {
				dp[book + 1][money] = dp[book][money];
				int prev = money - costs[book];
				if (prev >= 0) {
					// El número total de páginas que tenemos si compramos este libro.
					int newState = dp[book][prev] + pages[book];
					dp[book + 1][money] = Integer.max(dp[book + 1][money], newState);
				}
			}
		}
 
		// Imprimir la respuesta.
		System.out.println(dp[N][X]);
	}
}