Elección óptima P65534


Statement
 

pdf   zip

html

Angel, un buen amigo vuestro, tiene un camión que puede transportar un peso máximo W. Además tiene n objetos en casa, cada uno con peso wi y valor vi. Angel se marcha, así que se quiere llevar el subconjunto más valioso de objetos cuyo peso total no exceda W. Sin embargo, a Angel no le gusta calcular soluciones óptimas. ¿Le podéis ayudar?

Entrada

La entrada consiste en diversos casos, sólo con números enteros. Cada caso empieza con W y n, seguidos de n pares wi, vi. Asumid 1 ≤ W ≤ 1012, 1 ≤ n ≤ 100, 1 ≤ wi ≤ W, y 1 ≤ vi ≤ 100.

Salida

Para cada caso, escribid tres lineas. En la primera, escribid el valor total más grande posible. En la segunda, escribid el número de objetos del subconjunto óptimo. En la tercera, escribid en orden creciente y separados por espacios los índices (empezando en uno) de los objetos elegidos. Si hay más de una solución óptima, podéis escoger cualquiera de ellas.

Public test cases

  • Input

    10000 3
5000 20
8000 27
4000 10

10000 3
5000 20
8000 100
4000 10

1000000 2
900000 10
100000 20

1000000000000 10
100000000000 1
200000000007 2
300000000000 3
400000000001 4
500000000003 5
100000000000 1
200000000000 2
300000000000 3
400000000005 4
500000000000 5

    Output

    30
2
1 3
100
1
2
30
2
1 2
10
3
7 8 10
    • Information
    Author
    Salvador Roura
    Language
    Spanish
    Translator
    Salvador Roura
    Original language
    English
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++