Sesión 18

Clase del 23 de abril de 2020. Backtracking

Temas

Ejercicio: Encontrar todas las sumas posibles diferentes mayores o iguales a x en un vector. Entrada:

{1, 4, 5}
x = 5

Salida:

5, 6, 9, 10

Material de backtracking:

Ejemplo: Encontrar la suma mas grande menor o igual a x en un vector e imprimir la forma en que se llega al resultado.

Fuente: Problema del CD

Entrada

Primera linea indica x

Segunda linea es la cantidad de elementos en el vector.

Siguiente linea contiene los valores del vector

20
4
10  5  7  4

10 + 5 + 4 = 19

90
8
10  23  1  2  3  4  5  7

10 + 23 + 1 + 2 + 3 + 4 + 5 + 7 = 55

45
8
4  10  44  43  12  9  8  

4 + 10 + 12 + 9 + 8  = 45

Usar backtracking para generar todas las sumas posibles y elegir la mejor.

Last updated 5 years ago