PKU 3093 - Margaritas on the River Walk

Autor da análise: cesargmcesargm

Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=3093

Resumo

Dado um conjunto de elementos com custos vi e um valor máximo D, encontrar o número de subconjuntos com custo menor ou igual a D que são maximais (ou seja, não é possível adicionar outro elemento sem estourar o limite do custo).

Número de casos: $1 \le N \le 1000$
Número de elementos (Vendors): $1 \le V \le 30$
Dinheiro disponível: $1 \le D \le 1000$
Custo de cada elemento: $1 \le v_i$

IMPORTANTE: Não é dito no enunciado, mas caso todos os valores sejam maiores do que D (não é possível comprar nenhuma das bebidas), a resposta é 0, e não 1.

Solução

Primeiro, ordene os elementos em ordem crescente de valor.

Caso todos os elementos tenham valor maior que D, a resposta é 0.

Crie um vetor sum que guarda a soma dos primeiros i elementos.

Crie uma matriz PD que irá guardar de quantos jeitos (maximais) é possível pegar um subconjunto dos e primeiros elementos com custo no máximo d (obviamente a resposta do problema é PD[V][D]).

(1)
\begin{align} \textrm{PD}[e][d] = \left\{ \begin{array}{l} 1, \textrm{ se sum}[e] \leq d \textrm{ (\'{e} poss\'{i}vel colocar todos os elementos)}\\ 1, \textrm{ se } d = 0 \textrm{ (n\~{a}o colocar nenhum dos } e \textrm{ primeiros)}\\ 0, \textrm{ se } d \leq 0\\ \textrm{PD}[e-1][d-v_e] + \textrm{PD}[e-1][d], \textrm{ caso contr\'{a}rio (usar o elemento ou n\~{a}o)} \end{array} \right. \\ \end{align}

Obs: O fato das soluções serem maximais é garantido pelo primeiro caso da PD e pela ordenação dos elementos. Se os elementos não estiverem ordenados e o primeiro elemento tiver custo maior do que d, as soluções não-maximais não serão eliminadas. (os dois últimos casos da entrada abaixo são exemplos disso)

Testes

Entrada

5

6 25
8 9 8 7 16 5

30 250
1 2 3 4 5 6 7 8 9 10 11
12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30

4 10
11 12 13 14

7 25
26 8 9 8 7 16 5

7 25
25 8 9 8 7 16 5

Saída

1 15
2 16509438
3 0
4 15
5 16

Enquete

Qualidade do enunciado

Dificuldade do problema

Problema interessante

Discuta o problema

Add a New Comment
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License