Talent Show

Idea errónea común

Nótese que la siguiente solución es incorrecta: En vez de usar búsqueda binaria como hace la solución oficial, se puede hacer una mochila (knapsack). Se puede mantener un arreglo de talentos, donde $\texttt{talent}[i]$ es el peso mínimo requerido para crear una suma de talento de $i$ . Para asegurarnos de que cada vaca se use a lo sumo una vez y de que el orden de las vacas no importe, los índices de $\texttt{talent}$ se recorren de mayor a menor, y las $\texttt{cows}$ se recorren en el bucle externo; la implementación debería dejar esto claro. Esto maximiza el cociente $\frac{t}{w}$ como se desea. Luego, el cociente máximo de $\frac{t_i}{w_i}$ se puede hallar fácilmente recorriendo $\texttt{talent}$ e ignorando cualquier $w_i$ que sea menor que $W$ .

Mi código $\mathcal{O}(\text{Total talent } \cdot n)$ está abajo:

Mostrar código

C++


#include <bits/stdc++.h>
#define w first
#define t second
using namespace std;
 
const int inf = 2e9;
const int total_talent = 250000;
int n, W;
double ans = 0;
 
signed main() {
	ifstream cin("talent.in");
	ofstream cout("talent.out");
	cin >> n >> W;
	vector<pair<int, int>> cows(n);
	for (int i = 0; i < n; i++) cin >> cows[i].w >> cows[i].t;
	vector<int> talent(1e6 + 10, inf);
	talent[0] = 0;
	for (auto cow : cows)
		for (int i = total_talent; i >= 0; i--)
			if (talent[i] != inf)
				talent[i + cow.t] = min(talent[i + cow.t], talent[i] + cow.w);
	for (double T = 1; T < talent.size(); T++)
		if (talent[T] >= W && T / talent[T] > ans) ans = T / talent[T];
	cout << (int)(1000 * ans) << endl;
}

Sin embargo, aunque esto pasa todos los casos de prueba de USACO, hay un defecto fatal. Estamos hallando el peso mínimo requerido para cada suma de talento. ¿Qué pasa si el peso mínimo para una suma de talento es menor que el umbral de peso? Consideremos si el umbral sí es alcanzable con una suma de talento particular pero la DP concluyó que no. La DP nunca considera un peso un poco mayor, uno que pueda superar el umbral, como candidato para la respuesta. Esto significa que la DP falla en casos donde el escenario mencionado ocurre y es óptimo; un ejemplo es el siguiente:

La respuesta correcta es 375; la solución de arriba imprime 296.