Solução Informática Avançado - Semana 50 - Problema 1

Solução de Lúcio Cardoso

Este problema é o clássico Problema da Mochila (ou Knapsack), porém com algumas restrições adicionais que nos impossibilitam de resolver-lô da maneira tradicional.

Note que, como cada $v_i < 10^3$ e $N < 100$ , a resposta máxima será no máximo $10^5$ . Faremos então a seguinte Programação Dinâmica: Seja $dp[i][j]$ a menor soma de pesos possível para conseguir um valor total $j$ , considerando os livros desde 1 até $i$ . Assim,

$dp[i][j]$ = $\begin{cases} 0 & , \mbox{se j = 0 ou i = 0} \\ \min \big( dp[i - 1][j] , dp[i - 1][j - v_i] + w_i \big) & , \mbox{caso contrario (podemos usar ou nao o i-esimo livro)}\end{cases}$

Logo, a resposta para o problema é o maior valor possível $V$ tal que $dp[N][V] <= W$ . Ou seja, queremos conseguir o valor $V$ sem ultrapassar a capacidade da mochila.

A complexidade final será $\mathcal{O}(N \cdot V)$ , onde $V$ é a maior soma de $v_i$ possível. Confira o código para melhor entendimento:

	// Noic - Semana 50 - Avançado
	// Complexidade: O(N*V)

	#include <bits/stdc++.h>

	using namespace std;

	const int maxn = 110;
	const int maxv = 1e5+10; // maior resposta possível

	int w[maxn], v[maxn];

	int dp[maxn][maxv];

	int main(void)
	{
	int n, W;
	cin >> n >> W;

	for (int i = 1; i <= n; i++)
	cin >> w[i] >> v[i];

	// Casos Base
	for (int i = 0; i <= n; i++)
	{
	dp[i][0] = 0;
	for (int j = 1; j < maxv; j++)
	dp[i][j] = W+1; // por enquanto, daremos um valor grande
	}

	for (int i = 1; i <= n; i++)
	{
	for (int j = 1; j < maxv; j++)
	{
	// precisamos checar se é possível usar v[i]
	if (j >= v[i]) dp[i][j] = min(dp[i-1][j], dp[i-1][j-v[i]] + w[i]);
	else dp[i][j] = dp[i-1][j];
	}
	}

	int ans = 0;
	for (int i = 1; i < maxv; i++)
	if (dp[n][i] <= W) ans = i;

	cout << ans << "\n";
	}

view raw

noic-semana50-avanc.cpp

hosted with ❤ by GitHub

Solução de Lúcio Cardoso

dp[i][j] = \begin{cases} 0 & , \mbox{se j = 0 ou i = 0} \\ \min \big( dp[i - 1][j] , dp[i - 1][j - v_i] + w_i \big) & , \mbox{caso contrario (podemos usar ou nao o i-esimo livro)}\end{cases}

$dp[i][j]$ = $\begin{cases} 0 & , \mbox{se j = 0 ou i = 0} \\ \min \big( dp[i - 1][j] , dp[i - 1][j - v_i] + w_i \big) & , \mbox{caso contrario (podemos usar ou nao o i-esimo livro)}\end{cases}$