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 programme | Sortie 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.
