Embedded Files
Esse problema caiu na final brasileira da maratona de programação em 2015 : https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=702&page=show_problem&problem=5219
Mas foi traduzido para português e cadastrado no The Huxley: https://www.thehuxley.com/problem/613
O problema pede para maximizarmos a quantidade de pessoas de um partido e também maximizarmos a quantidade de pessoas do outro partido. Esse é o primeiro ponto a perceber, são duas otimizações. Uma para cada partido.
Vamos começar entendendo o exemplo dado:
2 3 2 55
20 30
40 30 1
2 3
1 3
A primeira linha indica que temos 2 membros no PD, 3 no Prism, 2 rivalidades e 55 de orçamento.
A segunda linha indica que os custos de subornar os dois membros do PD são 20 e 30, respectivamente.
A terceira linha indica que os custos para subornar os 3 membros do PRISM são 40, 30 e 1.
A quarta linha descreve a primeira rivalidade, nesse caso, entre o membro 2 do PD com o membro 3 do PRISM.
A quinta linha descreve a segunda e última rivalidade, nesse caso, entre o membro 1 do PD e o membro 3 do PRISM.
Uma forma que parece natural de modelar esse problema é como um grafo. Cada vértice seria um político e as arestas seriam as rivalidades entre eles:
Agora vamos tentar maximizar a quantidade de pessoas no PD. Inicialmente o PD possui 2 políticos. Temos 3 integrantes do prism para tentar subornar. Temos orçamento para subornar o 1 ou o 2, mas não ambos. Se subornarmos somente o 3, chegaríamos a uma situação que não seria possível, pois existe rivalidade entre o 3 e integrantes do PD.
Então, teríamos como solução de composição do PD:
- PD = { pd(1), pd(2) } // não subornar ninguém
- PD = { pd(1), pd(2), prism(1) } // subornando o prism(1)
- PD = { pd(1), pd(2), prism(2) } // subornando o prism(2)
As duas últimas soluções possuem 3 membros. Seriam essas todas as soluções possíveis?
E se subornarmos o 3? O problema é que ele não pode ficar junto nem do pd(1) e nem do pd(2). Mas e se subornarmos o pd(1) e o pd(2) ? Ou seja, se subornarmos todos esses 3, teríamos um custo de 20 + 30 + 1 = 51, o que caberia no nosso orçamento. Nessa situação, pd ficaria com apenas um elemento, pois o pd(1) e pd(2) estariam no PRISM:
- PD = { prism(3) }
Embora esse último conjunto encontrado não seja a melhor solução, ele seria uma das soluções possíveis. Nesse caso, a melhor solução que encontramos para PD foi 3 (que pode ser subornando o prism(1) ou subornando o prism(2) ).
O mesmo raciocínio podemos aplicar para maximizar o PRISM
Só que nesse caso a única possibilidade de aumentarmos o número de elementos do PRISM é fazendo exatamente o que fizemos no último passo. Ou seja, subornando pd(1), pd(2) e prism(3). Com isso, teríamos o PRISM com 4 integrantes:
- PRISM = { prism(1), prism(2), pd(1), pd(2) }
Pronto, encontramos a solução para o problema.
Agora é transformar isso em algoritmo.
Veja que se quisermos subornar pd(1), pd(2) ou prism(3), temos que subornar todos eles, caso contrário, nas iremos satisfazer as rivalidades. Logo, podemos encontrar todos os componentes conectados desse grafo (veja aqui como fazer isso). Em cada componente conectado, a gente conta quantos elementos existem em cada um dos partidos e qual seria o custo de subornar alguém do componente, ou seja, qual é a soma dos custos dos integrantes do componente.
No caso acima, teríamos 3 componentes:
Perceba que colocamos uma tupla com 3 valores para cada componente: (número de políticos do PD, número de políticos do PRISM, custo de subornar alguém do componente).
Para construirmos esses componentes, você pode encontrar os componentes usando um BFS. Durante a execução do BFS, você cria essa tupla de cada componente e adiciona a um vector.
Pronto .. nesse ponto, já temos todos os componentes. Agora falta otimizarmos nossas decisões. Perceba que o que precisamos fazer agora é em cada componente decidir se vamos subornar ou não.
Por exemplo, suponha que vamos maximizar o PD. No componente que contém os elementos { pd(1), pd(2), prism(3) }. Se não subornarmos ninguém, continuamos com os 55 de orçamento e teremos 2 pessoas no PD até o momento. Por outro lado, se subornarmos, então teríamos 1 pessoa no PD e 55-51 de orçamento.
Para cada componente, temos que decidir se vamos subornar ou não, e estamos sujeitos a um orçamento... opa ... mas esse é exatamente o problema da mochila.
Agora, o que precisamos fazer é resolver o problema da mochila maximizando a quantidade de políticos do PD e depois resolver de novo o problema da mochila maximizando a quantidade de políticos em PRISM. Com isso, o protótipo da sua função de programação dinâmica da mochila ficará parecida com:
/*component_idx - índice do componente que temos que decidir se vamos ou não subornarbudget - orçamento restanteparty - 0 para indicar o partido DP, 1 para indicar o PRISM*/int dp(int component_idx, int budget, int party)Bons códigos!!
Google Sites
Report abuse