Minimitzar el màxim de les sumes P23519

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.