Minimitzar el màxim de les sumes

Donats dos naturals m i n i un vector v d’n naturals, es vol trobar
quina és el mínim del màxim de les sumes dels trossos de v quan aquest
és tallat en m trossos.

Per exemple: Considereu m = 2, n = 4 i v = [12, 34, 67, 90]. Hi ha tres
maneres de tallar v en m trossos: [12|34, 67, 90], [12, 34|67, 90] i
[12, 34, 67|90]. En el primer cas, el primer tros suma 12 i el segon
suma 191. Per tant el màxim de les sumes és 191. Pel segon cas el màxim
de les sumes és 157, i pel tercer cas el màxim de les sumes és 113. Per
tant, el mínim dels màxims de les sumes és 113.

Resoleu el problema en tres passos:

1.  Primer, escriviu una funció
    bool has_max_sum(const vector<int>& v, int m, int x) que indiqui si
    es pot tallar v en m trossos de forma que el màxim de les sumes dels
    trossos sigui x o menys.

2.  Després, escriviu una funció
    int min_max_sum(const vector<int>& v, int m) que retorni el mínim
    dels màxims de les sumes de v en m trossos utilitzant has_max_sum
    astutament.

3.  Finalment, descriviu en un comentari a l’inici del programa quina és
    l’estratègia del vostre algorisme i quin és el seu cost.

Descarregueu el fitxer code.cc per trobar l’esquelet del codi i el
comentari i la implementació del programa principal. Podeu assumir que
n ≥ m ≥ 1, i que S, la suma dels elements del vector, cap en un int.

Informació del problema

Autoria: Jordi Petit i Jordi Cortadella

Generació: 2026-03-13T10:37:52.556Z

© Jutge.org, 2006–2026.
https://jutge.org
