PKU 3093 - Margaritas on the River Walk

Autor da análise: cesargm

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

Resumo

Dado um conjunto de elementos com custos v_i 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

oshiro 26 Apr 2009 17:13

Se não me engano, parece que neste problema deve-se imprimir a resposta com long long, contrariando o que diz o enunciado. Se for isso mesmo, seria bom deixar isso claro em algum lugar.

Re:

raphael_ribas 26 Apr 2009 17:58

Isso não aconteceu nessa questão.
Esse problema aconteceu com a 2731.

Last edited on 26 Apr 2009 19:49 by raphael_ribas Show more

Re:

cesargm 26 Apr 2009 22:31

Usei long long porque não conseguia passar, mas o que estava dando problema era o caso em que a resposta era 0. Com int aparentemente também passa. (obs: talvez o long long seja necessário para o vetor sum).

Outra idéia

natan_lima 26 Apr 2009 22:53

Fiz de um jeito diferente.

Tenho uma função F(at,n,custo) que devolve quantos conjuntos tem a partir de at com n elementos cuja a soma é custo.
Essa função pode ser calculada com uma pd simples:

F(at,n,custo)
    se n == 0 e custo == 0 devolva 1
    devolva F(at+1,n,cst) + F(at+1,n-1,cst-v[at])

Depois disso fica fácil.
Também ordenei a entrada em ordem não decrescente, e o número de soluções maximais pode ser obtido com a seguinte recursão:

X(at,custo) 
    para i de 1 até n
        para j de 0 até v[at]
            total += F(at+1,i,custo - j)
    devolva total + X(at,custo - v[at])

ou seja, a soma de todas as soluções que v[at] não cabe + as soluções em que v[at] está.

obs: não coloquei os casos bases das recursões para não ficar muito fácil.

Last edited on 26 Apr 2009 23:21 by natan_lima Show more

Uma idéia pior

piva 29 Apr 2009 14:38

A primeira idéia que eu passei tem uma dimensão a mais na pd (e por isso mesmo, é mais lenta), mas é "mais fácil" de codar por causa dos casos base. Eu tinha definido a subestrutura como T(pos, left, mini) onde pos é a posição que eu estou, left é o tanto que ainda cabe, e mini é o menor cara que eu não escolhi.

Passou em 0ms também, apesar de usar mais memória.