Brazalete de Dijes

Points: 100 (partial)

Time limit: 1.0s

Memory limit: 64M

Author:

FrankHG

Problem type

Allowed languages

C, C++, Java, Pascal, Python, VB

Bessie ha ido a la joyería del centro comercial y ha visto un brazalete de dijes. Por supuesto, ella quisiera llenarlo con los mejores dijes posibles de $N (1 <= N <= 3,402)$ ~N (1 <= N <= 3,402)~ dijes disponibles. Cada dije $i$ ~i~ tiene un peso $W_i (1 \leq W_i \leq 400)$ ~W_i (1 \leq W_i \leq 400)~ y una factor de 'deseabilidad' $D_i (1 \leq D_i \leq 100)$ ~D_i (1 \leq D_i \leq 100)~. Bessie puede únicamente soporta un brazalete de dijes cuyo peso sea menor que $M (1 \leq M \leq 12,880)$ ~M (1 \leq M \leq 12,880)~.

Dado el peso límite como una restricción y una lista de los dijes con sus pesos y factores de deseabilidad, deduzca la mayor suma posible de deseabilidades.

Entrada

Línea 1: Dos enteros separados por espacio: $N$ ~N~ y $M$ ~M~.
Líneas 2..N+1: La línea i+1 describe el dije i con dos enteros separados por espacio: $W_i$ ~W_i~ y $D_i$ ~D_i~.

Ejemlo de Entrada

Detalles de la Entrada

Cuatro dijes potenciales, peso máximo 6

Salida

Línea 1: Un solo entero que es la suma más grande de deseabilidades de dijes que puede ser obtenida dadas las restricciones de peso

Ejemplo de Salida

Detalles de la Salida

Sin el segundo dije posible, el valor $4+12+7=23$ ~4+12+7=23~ es el valor más alto con un peso $1+2+3<=6$ ~1+2+3<=6~

Comments

1

Brayan080808 commented on Aug. 8, 2022, 2:50 a.m.

Alguien me ayudar con esto, se que es el problema de la mochila que lo e echo 100 veces pero no logro que entre en tiempo