Sesión 17

Clase del 21 de abril de 2020. Intro a DFS

Temas

Introducción a DFS

#include <iostream>
#include <vector>

using namespace std;

// Funcion para realizar la DFS
void calcula_sumas(int pos, int sum, vector<int>& valores, int objetivo) {
    // Revisar si el estado actual es una respuesta
    if (sum >= objetivo) {
        cout << sum << " ";
    }
    // Revisar estado invalido
    if (pos >= valores.size()) {
        return;
    }
    // Probar con todas las opciones disponibles
    // a) NO incluir el elemento actual en la suma
    calcula_sumas(pos + 1, sum, valores, objetivo);
    // b) SI incluir el elemento actual en la suma
    calcula_sumas(pos + 1, sum + valores[pos], valores, objetivo);
    // NOTA: cuando se tienen varias opciones, se puede hacer los siguiente
    // for (int opcion = 0; opcion < opciones.size(); opcion++) {
    //      hacer algo con los valores de opciones[opcion]
    //      calcula_sumas(...)   
    // }
}

int main() {
    int n;
    int x;
    cin >> n >> x;
    vector<int> valores(n);
    for (int i = 0; i < valores.size(); i++) {
        cin >> valores[i];
    }
    calcula_sumas(0, 0, valores, x);


    return 0;
}

Códigos vistos en clase

ooi-2020/curso-avanzado/sesion-17 at master · omioaxaca/ooi-2020GitHub

Video: https://youtu.be/YpQ5754BqKo