9
votes

Étant donné un ensemble S, trouvez tous les sous-ensembles maximaux dont la somme <= k

Ceci est une question d'entrevue facebook que j'ai rencontrée sur un portail en ligne.

Étant donné un ensemble S, trouvez tous les sous-ensembles maximaux dont la somme <= k. Par exemple, si S = {1, 2, 3, 4, 5} et k = 7 La sortie est: {1, 2, 3} {1, 2, 4} {1, 5} {2, 5} {3, 4}

Astuces:

La sortie ne contient aucun ensemble qui est un sous-ensemble d'autres.
si x = {1, 2, 3} est l'une des solutions, tous les sous-ensembles de x {1} {2} {3} {1, 2} {1, 3} {2, 3} sont omis .
Les commandes lexicographiques peuvent être utilisées pour le résoudre.
Des idées Comment cela pourrait-il être résolu?

algorithm arrays set computer-science

2 commentaires

peut s contenir une valeur répétée? tels que s = {1, 2, 3, 3, 4, 5} ?


                                        
                                                                            @Seph, non, c'est  définir  = pas de duplicates



                                    
                    6 Réponses :
                    
                                            
                            
                                
                                    5
 votes
                                
                            
                            
                                
                                     J'ai une idée - vous avez besoin d'un arbre. 

 Si vous avez donné une entrée de  {1, 2, 3, 4, 5} , et vous recherchez des sous-ensembles maximaux - vous devez construire une arborese à partir des plus grands nombres, et toujours Développez  pendant que somme <= k  (alors ne vous arrêtez pas sur 4-2, mais descendez à 1 pour obtenir 4-2-1). 

 Ainsi, les nœuds à partir de 5 seraient:  5-1  /  5-2  - Seuls ceux-ci 2 ont une somme <= 7 

 À partir de 4:  4-3  /  4-2-1  / 4-1 (sous-ensemble de précédent) 

 À partir de 3:  3-2-1  / 3-1 (sous-ensemble de précédent) 

 à partir de 2: 2-1 (sous-ensemble de 3-2-1) 

 à partir de 1: 1 (sous-ensemble de 2-1) 

 Ensuite, vous pouvez trier les sorties valides et obtenir {1, 2, 3} {1, 2, 4} {1, 5} {2, 5} {3, 4}                                 


                                                                    
                                    
                                    
                                        2 commentaires
                                        
                                                                                            
                                                    Pouvez-vous s'il vous plaît proposer un algorithme ??                                                
                                                
                                                                                            
                                                    Nous enregistrons les nœuds contenant les sous-ensembles (satisfaisant la règle <= 7) dans une pile ou une file d'attente ou une matrice et éliminez les doublons et imprimez le tableau.                                                
                                                
                                                                                    
                                    
                                                            

                        

                        
                                            
                            
                                
                                    1
 votes
                                
                            
                            
                                
                                     Ceci est un problème de Powerset. Récemment, j'ai trouvé  Ce site  sur les algorithmes et il fait fondre mon imagination: d'où la solution Powerset / Combinaisons suit. Vous pouvez simplement copier, coller et exécuter le programme.  XXX                                  

                                                                    
                                    
                                    
                                        2 commentaires
                                        
                                                                                            
                                                    @Raman Bhatia est là une raison pour laquelle vous n'avez pas accepté cette réponse? heureux de vous aider.                                                
                                                
                                                                                            
                                                    Cette solution semble très complexe et difficile à comprendre avec des commentaires / explications supplémentaires                                                
                                                
                                                                                    
                                    
                                                            
                        
                        
                                            
                            
                                
                                    0
 votes
                                
                            
                            
                                
                                     Je suis désolé d'avoir une copie si tard. Mais que diriez-vous de faire cela? 

 1) Construisez une structure de tas min-thep à partir du tableau / réglage donné 

 2) Traverser la structure de la racine et continuez à soustraire la valeur au nœud que vous visitez. Une fois que vous avez dépassé la somme requise (curr_sum> k), émettez ce chemin de retour sur le parent et prenez un autre chemin (cela peut être effectué de manière récursive). 

 3) Si la récupération de retour vous ramène au nœud d'origine que vous avez démarré, implémentez l'ensemble de l'algorithme de Root-> Nœud gauche. 

 4) Faites deux étapes (2) et (3) ci-dessus mais avec un tas de max-max maintenant. 

 Je suis nouveau dans les algorithmes et les structures de données, et je n'ai commencé que de lire Intro à Algos-Cormen. Cela pourrait être une solution défectueuse, mais je serais plus qu'heureux si quelqu'un sort de la faute pour moi :)                                 

                                                                    
                                    
                                    
                                        0 commentaires
                                        
                                                                                    
                                    
                                                            
                        
                        
                                            
                            
                                
                                    2
 votes
                                
                            
                            
                                
                                     Je sais qu'il est tard pour répondre, mais je pense avoir trouvé une solution simple à ce problème. Nous énumérons des sous-ensembles de  S  dans l'ordre lexicographique à l'aide de la backtracking et de vérifier la somme  du sous-ensemble généré jusqu'à présent. 
 Lorsque la somme  dépasse  > k , la pièce intéressante vient: Nous devons vérifier si le sous-ensemble  généré  est un sous-ensemble approprié d'éléments signalés précédemment.  
 une solution est de garder tout le Des sous-ensembles signalés et vérifient l'inclusion, mais c'est gaspillé.  
 Au lieu de cela, nous calculons la différence entre le  k  et la somme . / code>. S'il y a un élément  E  dans  s  tel que  e pas dans le sous-ensemble  et  e <= (k - somme) , alors, l'ensemble que nous avons généré est un sous-ensemble approprié d'un sous-ensemble précédemment rapporté, et nous pouvons sauter en toute sécurité.  
 Voici le programme de travail complet dans un ancien C ++, démontrant l'idée:   xxx  
 La sortie est tout sous-sols maximum dans l'ordre lexicographique, une par ligne:   xxx                                  


                                                                    
                                    
                                    
                                        0 commentaires
                                        
                                                                                    
                                    
                                                            

                        

                        
                                            
                            
                                
                                    1
 votes
                                
                            
                            
                                
                                     Une ancienne question mais toujours intéressante. 
 Voici une solution Java 8 récursive, avec une approche "permutationnelle".  p> 
 optimisé pour un code plus propre et plus court plutôt que des performances - par exemple le Le tri et la taille ne devraient avoir lieu qu'une fois.  p>  xxx  pré> 
 pour le tester:  p> 
public static void main(String[] args) {
    new SubsetFinder()
        .findSubsets(ImmutableList.of(1, 2, 3, 4, 5), 7)
        .forEach(System.out::println);
}

                                

                                                                    
                                    
                                    
                                        0 commentaires
                                        
                                                                                    
                                    
                                                            
                        
                        
                                            
                            
                                
                                    1
 votes
                                
                            
                            
                                
                                     L'algorithme est le suivant: 

 à partir du sous-ensemble vide. 
 cycle via une matrice d'origine à partir du début (en supposant que la matrice est déjà triée dans l'ordre croissant) jusqu'à ce que les courantsums soient moins ou moins égaux. 
 Si l'élément actuel ajouté aux courantsum est inférieur à la somme cible, ajoutant à l'élément de courant de sous-ensemble actuel et à l'exécution de la récursivité à partir de l'élément suivant. 
 Cycle de rupture de courant Si la somme actuelle dépasse les tagies. 
 Si nous ne pouvons pas ajouter plus d'éléments dans le sous-ensemble actuel, nous vérifions si c'est  maximal  et l'imprimer dans ce cas. 
 Pour déterminer les sous-ensembles maximaux, nous pouvons comparer l'élément de tableau d'origine et de sous-ensemble actuel par élément, à la recherche du premier décalage. Si l'élément d'indice d'inadéquation d'abord est supérieur à la différence entre les courantsum et les tachetsum, le sous-ensemble est maximal et doit être imprimé. 
  solution de travail sur Java est ci-dessous:   xxx                                  

                                                                    
                                    
                                    
                                        0 commentaires

Articles qui pourrait vous intéresser : Calculer la différence dans l'échelle d'évaluation alphabétique Complexité de Trouver tous les multiples de 3 et 5 entre 1 et 10 000 000 Ma vérification pour savoir si un graphique est un arbre binaire renvoie toujours faux Comment trouver le nombre d'itérations de l'algorithme de recherche binaire?