La programmation 0/1, ou programmation fractionnaire 0/1, est une classe de problèmes d'optimisation. Elle implique la sélection d'un sous-ensemble d'éléments, où chaque élément a deux attributs, disons \(a_i\) et \(b_i\). L'objectif est de maximiser (ou minimiser) le ratio \(\frac{\sum a_i \times d_i}{\sum b_i \times d_i}\), sous certaines contraintes, souvent le choix d'exactement \(k\) éléments.

La stratégie clé pour résoudre ces problèmes est la recherche binaire sur la valeur du ratio. Supposons que nous cherchions à maximiser le ratio. Pour une valeur médiane hypothétique \(mid\), nous pouvons reformuler l'objectif comme suit :

Voici un exemple d'implémentation pour la vérification :

#include <vector>
#include <algorithm>
#include <functional>

struct Item {
    double weight_diff;
    int id;
};

bool compareItems(const Item& a, const Item& b) {
    return a.weight_diff > b.weight_diff;
}

bool check(double mid, int n, int k, const std::vector<double>& a, const std::vector<double>& b, std::vector<Item>& weighted_items) {
    weighted_items.clear();
    for (int i = 0; i < n; ++i) {
        weighted_items.push_back({a[i] - mid * b[i], i});
    }

    std::sort(weighted_items.begin(), weighted_items.end(), compareItems);

    double current_sum = 0;
    for (int i = 0; i < k; ++i) {
        current_sum += weighted_items[i].weight_diff;
    }
    return current_sum >= 0;
}

// Exemple d'utilisation dans une recherche binaire
/*
double low = 0, high = some_upper_bound;
for(int iter = 0; iter < 100; ++iter) { // 100 iterations pour la précision
    double mid = low + (high - low) / 2;
    std::vector<Item> current_weighted_items;
    if (check(mid, n, k, a, b, current_weighted_items)) {
        low = mid; // Le ratio mid est possible, on essaie plus haut
    } else {
        high = mid; // Le ratio mid n'est pas possible, on essaie plus bas
    }
}
// Le résultat est 'low'
*/

Variantes Courantes

1. Contrainte de Quantité Minimale

Dans certains problèmes, il peut y avoir une contrainte supplémentaire, comme la somme des \(b_i \times d_i\) doit être au moins \(K\). La vérification \(check(mid)\) doit alors s'assurer que non seulement le ratio est atteint, mais aussi que la contrainte est satisfaite. Cela peut souvent être résolu avec une programmation dynamique de type sac à dos (knapsack).

Pour un sac à dos avec capacité \(K\) et où l'on cherche à maximiser \(\sum (a_i - mid \times b_i) \times d_i\) tout en respectant la contrainte \(\sum b_i \times d_i \ge K\), on peut adapter la DP. Si l'on utilise \(a_i\) comme "poids" et \(b_i - mid \times a_i\) comme "valeur", et que la capacité est \(K\), la DP peut être formulée comme suit :

#include <vector>
#include <algorithm>
#include <map>

// dp[i][j] : la valeur maximale en sélectionnant des objets parmi les i premiers,
// avec une somme de b_i (ou assimilé) égale à j.
// Ici, on adapte pour l'objectif a_i - mid * b_i et contrainte sur b_i.

bool check_with_dp(double mid, int n, int min_b_sum, const std::vector<double>& a, const std::vector<double>& b, std::vector<std::vector<double>>& dp) {
    // Initialisation de dp
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= min_b_sum; ++j) {
            dp[i][j] = -1e18; // Utiliser une valeur très petite pour indiquer l'inaccessibilité
        }
    }
    dp[0][0] = 0;

    for (int i = 0; i < n; ++i) {
        double current_val = a[i] - mid * b[i];
        int current_b = static_cast<int>(b[i]); // Assumant que b[i] sont des entiers pour la DP

        for (int j = 0; j <= min_b_sum; ++j) {
            if (dp[i][j] < -1e17) continue; // Si l'état n'est pas atteignable

            // Option 1: Ne pas choisir l'objet i
            dp[i + 1][j] = std::max(dp[i + 1][j], dp[i][j]);

            // Option 2: Choisir l'objet i
            int next_b_sum = std::min(j + current_b, min_b_sum); // Cap à min_b_sum
            dp[i + 1][next_b_sum] = std::max(dp[i + 1][next_b_sum], dp[i][j] + current_val);
        }
    }

    // Vérifier si le maximum atteint pour une somme >= min_b_sum est positif
    double max_val = -1e18;
    for (int j = min_b_sum; j <= min_b_sum; ++j) { // En fait, on veut vérifier dp[n][j] pour tout j >= min_b_sum. Si la capacité est fixe, on regarde dp[n][min_b_sum]
        max_val = std::max(max_val, dp[n][j]);
    }
     // Correction : La logique précédente est pour une somme EXACTEMENT min_b_sum.
     // Pour >= min_b_sum, on doit s'assurer que le max sur tous les j >= min_b_sum est >= 0.
     // Si la capacité est réellement min_b_sum, alors on regarde dp[n][min_b_sum].
     // Si on utilise la version avec capping à min_b_sum, alors on regarde dp[n][min_b_sum].

    // Pour la contrainte "somme des b_i >= K"
    // Il faut soit une DP avec une capacité plus grande, soit une DP où l'on considère
    // que si la somme dépasse K, on la traite comme K.
    // L'exemple de code original utilise une approche de capping.
    // Si dp[n][min_b_sum] >= 0, cela signifie qu'on peut atteindre une somme de b_i pondérés
    // jusqu'à min_b_sum, avec une valeur totale pondérée non négative.

    return dp[n][min_b_sum] >= 0;
}

2. Structures Arborescentes

Lorsque les éléments sont organisés dans une structure arborescente et que les sélections doivent respecter les relations parent-enfant (par exemple, si un enfant est choisi, son parent doit l'être), on utilise souvent une programmation dynamique sur arbres combinée à la recherche binaire.

Soit \(dp[x][j]\) la valeur maximale obtenue dans la sous-arborescence de \(x\), en sélectionnant \(j\) éléments. La transition implique de combiner les résultats des sous-arborescences des enfants.

#include <vector>
#include <algorithm>

// Supposons que graph[x] contient les enfants de x
std::vector<std::vector<int>> graph;
std::vector<double> item_a, item_b; // Attributs a_i et b_i
double current_mid;
int max_selections; // k

// dp_tree[node][count] : meilleure valeur pondérée dans la sous-arborescence de 'node'
// en sélectionnant 'count' éléments.
std::vector<std::vector<double>> dp_tree;

int dfs_tree(int u) {
    // Initialisation pour le noeud courant u
    dp_tree[u].assign(max_selections + 1, -1e18); // Initialiser avec une très petite valeur
    if (max_selections >= 1) { // Si on peut sélectionner au moins 1 élément
        dp_tree[u][1] = item_a[u] - current_mid * item_b[u]; // Valeur pondérée de u si choisi
    }
    int subtree_size = 1; // Compte le nombre total d'éléments potentiels dans la sous-arborescence

    for (int v : graph[u]) {
        int child_subtree_size = dfs_tree(v);
        std::vector<double> next_dp(max_selections + 1, -1e18);

        // Combiner les résultats de u avec ceux de la sous-arborescence de v
        for (int i = 1; i <= subtree_size; ++i) { // Nombre d'éléments choisis dans la partie déjà traitée de la sous-arborescence de u
            if (dp_tree[u][i] < -1e17) continue;
            for (int j = 0; j <= child_subtree_size; ++j) { // Nombre d'éléments choisis dans la sous-arborescence de v
                if (dp_tree[v][j] < -1e17) continue;
                if (i + j <= max_selections) {
                    next_dp[i + j] = std::max(next_dp[i + j], dp_tree[u][i] + dp_tree[v][j]);
                }
            }
        }
        dp_tree[u] = next_dp; // Mettre à jour le dp de u
        subtree_size += child_subtree_size;
        subtree_size = std::min(subtree_size, max_selections); // Ne pas dépasser la limite
    }
    return subtree_size;
}

bool check_tree(double mid, int n, int k, const std::vector<double>& a, const std::vector<double>& b, const std::vector<std::vector<int>>& adj) {
    current_mid = mid;
    max_selections = k;
    graph = adj; // Assigner le graphe
    item_a = a;
    item_b = b;
    dp_tree.assign(n, std::vector<double>(k + 1));

    // Supposons que la racine est 0 (ou 1 selon l'indexation)
    int total_nodes_possible = dfs_tree(0); // Ou la racine de l'arbre

    // Vérifier si la meilleure valeur pour k éléments est non négative
    return dp_tree[0][k] >= 0;
}

3. Détection de Cycle Négatif

Pour trouver un cycle dans un graphe où la somme des poids des arêtes divisée par le nombre de nœuds du cycle est minimale, on peut encore utiliser la recherche binaire. L'astuce consiste à modifier les poids des arêtes. Si nous cherchons un ratio minimum \(mid\), nous pouvons transformer chaque poids d'arête \(w\) en \(w - mid\). Ensuite, nous vérifions s'il existe un cycle négatif dans ce graphe transformé en utilisant un algorithme comme Bellman-Ford ou SPFA.

#include <vector>
#include <algorithm>
#include <limits>

struct Edge {
    int from, to;
    double weight;
};

std::vector<Edge> edges;
std::vector<double> dist;
std::vector<int> visit_count;
int num_nodes;

bool has_negative_cycle(double mid) {
    dist.assign(num_nodes + 1, 0.0); // Distance initiale à 0 pour tous les nœuds
    visit_count.assign(num_nodes + 1, 0);
    std::vector<bool> in_queue(num_nodes + 1, false); // Pour optimiser SPFA

    std::vector<int> q; // Utilisation de std::vector comme file pour SPFA

    // Initialiser SPFA en ajoutant tous les nœuds à la file
    for (int i = 1; i <= num_nodes; ++i) {
        q.push_back(i);
        in_queue[i] = true;
    }

    int head = 0;
    while(head < q.size()){
        int u = q[head++];
        in_queue[u] = false; // Marquer comme retiré de la file

        // Parcours des arêtes sortantes de u
        for(const auto& edge : edges) {
            if (edge.from == u) {
                double effective_weight = edge.weight - mid;
                if (dist[edge.to] > dist[u] + effective_weight) {
                    dist[edge.to] = dist[u] + effective_weight;
                    visit_count[edge.to]++;

                    if (visit_count[edge.to] >= num_nodes) {
                        return true; // Cycle négatif détecté
                    }

                    if (!in_queue[edge.to]) {
                        q.push_back(edge.to);
                        in_queue[edge.to] = true;
                    }
                }
            }
        }
    }
    return false; // Pas de cycle négatif détecté
}

// Dans la recherche binaire :
/*
double low = 0, high = some_max_weight;
for(int iter = 0; iter < 100; ++iter) {
    double mid = low + (high - low) / 2;
    if (has_negative_cycle(mid)) {
        // Si un cycle négatif existe, cela signifie que le ratio moyen peut être inférieur à mid.
        // On essaie donc de trouver un ratio encore plus petit.
        high = mid;
    } else {
        // Sinon, le ratio moyen doit être au moins mid.
        low = mid;
    }
}
// Le résultat est 'high' (ou 'low' si on cherche le minimum)
*/

4. Problèmes avec Intervalles et RMQ

Certains problèmes peuvent impliquer de trouver un sous-intervalle qui maximise (ou minimise) un certain ratio, avec des contraintes sur la longueur de l'intervalle. Cela peut être résolu avec la recherche binaire combinée à des structures de données comme les files monotones (deque) et la requête de minimum/maximum sur intervalle (RMQ).

#include <vector>
#include <deque>
#include <algorithm>
#include <cmath>

// Structure pour le RMQ (Sparse Table)
struct RMQ {
    std::vector<std::vector<double>> st_min, st_max;
    std::vector<int> log_table;
    int n;

    void build(const std::vector<double>& arr) {
        n = arr.size();
        log_table.resize(n + 1);
        log_table[1] = 0;
        for (int i = 2; i <= n; ++i) log_table[i] = log_table[i / 2] + 1;

        int k = log_table[n];
        st_min.assign(n, std::vector<double>(k + 1));
        st_max.assign(n, std::vector<double>(k + 1));

        for (int i = 0; i < n; ++i) {
            st_min[i][0] = arr[i];
            st_max[i][0] = arr[i];
        }

        for (int j = 1; j <= k; ++j) {
            for (int i = 0; i + (1 << j) <= n; ++i) {
                st_min[i][j] = std::min(st_min[i][j - 1], st_min[i + (1 << (j - 1))][j - 1]);
                st_max[i][j] = std::max(st_max[i][j - 1], st_max[i + (1 << (j - 1))][j - 1]);
            }
        }
    }

    double query_min(int l, int r) { // [l, r] inclus
        int j = log_table[r - l + 1];
        return std::min(st_min[l][j], st_min[r - (1 << j) + 1][j]);
    }
    double query_max(int l, int r) { // [l, r] inclus
        int j = log_table[r - l + 1];
        return std::max(st_max[l][j], st_max[r - (1 << j) + 1][j]);
    }
};

RMQ rmq_solver;
std::vector<double> values; // Les a_i

bool check_interval(double mid, int n, int min_len, int max_len) {
    // La logique ici est complexe et dépend des contraintes exactes.
    // Elle implique souvent de balayer un point de fin d'intervalle et d'utiliser
    // une deque pour maintenir les points de début possibles optimaux,
    // tout en utilisant RMQ pour vérifier les conditions sur les sous-intervalles.

    // Exemple simplifié : trouver si un sous-intervalle [i, j] existe tel que
    // (max(a[p]) - min(a[p])) / (j - i + 1) <= mid pour i <= p <= j
    // ce qui se reformule en (max(a[p]) - min(a[p])) <= mid * (j - i + 1)

    // On peut transformer les valeurs pour la recherche binaire : a[i] - mid * i
    // et chercher un intervalle avec une différence minimale entre max et min de ces nouvelles valeurs.

    // Un exemple conceptuel avec deque et RMQ pour une contrainte spécifique :
    std::deque<int> dq;
    std::vector<double> transformed_values(n);
    for(int i=0; i<n ...="" avec="" complexe="" condition="" contraintes="" de="" deque="" est="" et="" exemple="" false="" g="" intervalle="" it="" les="" logique="" longueur="" mid="" optimisations="" placeholder="" pour="" remplie="" retourner="" return="" rmq_solver.build="" si="" transformation="" transformed_values="" trouver="" true.="" un="" une="" valide="" values=""></n>

En résumé, la programmation fractionnaire 0/1 est un problème puissant qui se résout efficacement par recherche binaire. Les difficultés résident souvent dans la conception de la fonction de vérification (check), qui peut nécessiter des techniques avancées comme la programmation dynamique, les arbres, la détection de cycles négatifs, ou des structures de données segmentaires.