Nous utilisons des cookies pour améliorer votre expérience. En poursuivant votre navigation sur ce site, vous acceptez l'utilisation de cookies.


Politique de confidentialité

Trouver une somme de valeurs égales à une valeur donnée - Programmation compétitive

 

Trouver une somme de valeurs égales à une valeur donnée - Programmation compétitive

Dans la leçon sur l'addition et la soustraction, un enseignant d'une école primaire a utilisé un ensemble de valeurs, puis donne aux élèves une valeur somme et leur demande s'ils peuvent former cette valeur à partir de l'ensemble donné (Trouver une somme de valeurs égale à somme)

Entrée

La première ligne contient deux valeurs somme et n. La deuxième ligne contient n valeurs qui forment l'ensemble.

Sortie

Oui, s'il existe un tel sous-ensemble de valeurs, sinon Non .

  Exemples
Entrée du programmeSortie du programme
15 5
7 2 8 6 9
Oui
0 3
2 5 6
Oui
15 4
1 2 7 3
Non

Solution naive (Récursive)

Il y a deux cas :

  •  Inclure le dernier élément et maintenant la somme requise = somme - valeur du "dernier" élément et nombre d'éléments = nombre total d'éléments - 1
  •  Ignorer le "dernier" élément et maintenant la somme requise = somme et nombre d'éléments = nombre total d'éléments - 1
#include <iostream>
#include <vector>

using namespace std;

bool solution(vector<int> vals, int n, int somme){
 
    // cas de base
    if (somme == 0)
        return true;

    if (n == 0)
        return false;
 
    // Si le dernier élément est supérieur à somme, ignorez-le
    if (vals[n - 1] > somme)
        return solution(vals, n - 1, somme);
 
    // sinon, vérifiez si somme peut être obtenu par l'un des éléments suivants
    // (a) y compris le dernier élément
    // (b) exclure le dernier élément
    return solution(vals, n-1, somme) || solution(vals, n-1, somme-vals[n-1]);
}

int main()
{
    int somme, n, val;
    cin >> somme >> n;
    vector<int> valeurs;
    for(int i=0; i<n; i++){
        cin >> val;
        valeurs.push_back(val);
    }

    solution(valeurs,n,somme) ? cout << "Oui" : cout << "Non";

    return 0;
}
                    
import sys

def solution(vals, n, somme):
 
    # cas de base
    if (somme == 0):
        return True

    if (n == 0):
        return False
 
    # Si le dernier élément est supérieur à somme, ignorez-le
    if (vals[n - 1] > somme):
        return solution(vals, n - 1, somme)
 
    # sinon, vérifiez si somme peut être obtenu par l'un des éléments suivants
    # (a) y compris le dernier élément
    # (b) exclure le dernier élément
    return solution(vals, n-1, somme) or solution(vals, n-1, somme-vals[n-1])



somme,n = map(int, sys.stdin.readline().strip().split())
valeurs=list(map(int, sys.stdin.readline().strip().split()))

print("Oui" if solution(valeurs,n,somme) else "Non")
                    

La solution ci-dessus peut essayer tous les sous-ensembles d'un ensemble donné dans le pire des cas. Par conséquent, la complexité temporelle de la solution ci-dessus est exponentielle. Le problème est en fait NP-Complet (il n'y a pas de solution polynomiale connue pour ce problème).

Solution (Programmation dynamique)

Pour résoudre le problème en temps pseudo-polynomial nous utilisons la programmation dynamique.

Nous allons donc créer un tableau 2D de taille (n + 1) * (somme+ 1) de type booléen. L'état DP[i][j] sera vrai s'il existe un sous-ensemble d'éléments de vals[0….i] avec la valeur somme = 'j'. L'approche du problème est :

  •  Cela signifie que si l'élément actuel a une valeur supérieure à la "valeur de la somme actuelle", nous copierons la réponse pour les cas précédents
  •  Et si la valeur de la somme actuelle est supérieure au 'ième' élément, nous regarderons si l'un des états précédents a déjà connu la somme='j' OU si l'un des états précédents a connu une valeur 'j - vals[i]', ce qui résoudra notre problème.
#include <iostream>
#include <vector>

using namespace std;

bool solution(vector<int> &vals, int n, int somme){
 
    int DP[n+1][somme+1];
     
    // Si somme vaut 0, alors la réponse est vraie
    for (int i = 0; i <= n; i++)
        DP[i][0] = true;
         
    // Si la somme n'est pas 0 et que l'ensemble est vide, 
    // alors la réponse est fausse
    for (int i = 1; i <= somme; i++)
         DP[0][i]= false;
             
    // Remplir le tableau des sous-ensembles de manière ascendante
    // Bottom-up
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= somme; j++) {
            if (j<vals[i-1])
                DP[i][j] = DP[i-1][j];
            if (j>= vals[i-1])
                DP[i][j] = (DP[i-1][j] || DP[i - 1][j-vals[i-1]]);
        }
    }
    
    return DP[n][somme];
}

int main()
{
    int somme, n, val;
    cin >> somme >> n;
    vector<int> valeurs;
    for(int i=0; i<n; i++){
        cin >> val;
        valeurs.push_back(val);
    }

    solution(valeurs,n,somme) ? cout << "Oui" : cout << "Non";

    return 0;
}
                    
import sys

def solution(vals, n, somme):
     
    DP =([[False for _ in range(somme + 1)]
            for _ in range(n + 1)])
     
    # Si somme vaut 0, alors la réponse est vraie
    for i in range(n + 1):
        DP[i][0] = True
         
    # Si la somme n'est pas 0 et que l'ensemble est vide, 
    # alors la réponse est fausse
    for i in range(1, somme + 1):
         DP[0][i]= False
             
    # Remplir le tableau des sous-ensembles de manière ascendante
    # Bottom-up
    for i in range(1, n + 1):
        for j in range(1, somme + 1):
            if j < vals[i-1]:
                DP[i][j] = DP[i-1][j]
            if j>= vals[i-1]:
                DP[i][j] = (DP[i-1][j] or DP[i - 1][j-vals[i-1]])
    
    return DP[n][somme]


somme,n = map(int, sys.stdin.readline().strip().split())
valeurs=list(map(int, sys.stdin.readline().strip().split()))

print("Oui" if solution(valeurs,n,somme) else "Non")
                    
Complexité :
  •  Complexité temporelle : O(somme*n), où somme est la « somme cible » et « n » est la taille du tableau des valeurs.
  •  Complexité spatiale : O(somme*n), car la taille du tableau 2D est somme*n.

Partager ce cours avec tes amis :
Rédigé par ESSADDOUKI Mostafa
ESSADDOUKI
The education of the 21st century opens up opportunities to not merely teach, but to coach, mentor, nurture and inspire.