Brazalete de Dijes.

Points: 100 (partial)

Time limit: 1.0s

Memory limit: 64M

Author:

FrankHG

Problem types

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 \leq N \leq 3,402)$ ~N (1 \leq N \leq 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$ ~i+1~ describe el dije i con dos enteros separados por espacio: $W_i$ ~W_i~ y $D_i$ ~D_i~.

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 Entrada

Detalles de la Entrada: Cuatro dijes potenciales, peso máximo 6.

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\leq6$ ~1+2+3\leq6~

Comments

0

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