XOR de valeurs présentes dans le sous-ensemble du tableau

Question

Étant donné un tableau de A de taille n contenant uniquement des entiers positifs. Soit l le plus grand nombre du tableau A. Générer un tableau B de taille 0 à 1 tel que B [j] soit la taille du plus grand sous-ensemble du tableau A dont la valeur XOR est égale à j.

Contraintes: Taille du tableau A peut être de 1 à 10000. éléments dans le tableau A peut varier de 1 à 1000.

Par exemple: si le tableau A a (1,2,3,4) alors le tableau B serait généré comme ci-dessous.

B (0) = 3 comme le plus grand sous-ensemble ayant une valeur 0 est XOR (1,2,3) et sa taille 3.

B (1) = 2 comme le plus grand sous-ensemble ayant une valeur XOR 1 est (2,3) et sa taille 2.

B (2) = 2, comme le plus grand sous-ensemble ayant une valeur XOR 2 est (1,3) et sa taille 2.

B (3) = 2, comme le plus grand sous-ensemble ayant la valeur XOR 3 est (1,2) et a la taille 2.

B (4) = 4 comme le plus grand sous-ensemble ayant la valeur XOR 4 est (1,2,3,4) et a la taille 4

Mon approche de force brute: Générer tous les sous-ensembles non vides du tableau A et calculer XOR de chaque sous-ensemble et enregistrer le sous-ensemble de taille maximale ayant la valeur XOR j dans B [j].

Y a-t-il une approche plus efficace pour ce faire?

Answer 1

je crois que cela fonctionnerait, j'ai ajouté des commentaires pour aider

#include <iostream> 
using namespace std; 
#define max(a, b) (a>b?a:b) 
int dp[10005][1001]= {0}; 
int main() { 
    // your code goes here 
    int n, a[10005]={0}, m, i,j, ans[1005]={0}; 
    // n denotes number of elements in array, m denotes the range(0, m) where you want to loop 
    scanf("%d%d",&n,&m); 
    for(i=1; i<=n; i++){ 
     // taking input 
     scanf("%d",&a[i]); 
    } 
    for(i=0;i<=10000;i++){ 
     for(j=0;j<=1000;j++){ 
      dp[i][j] = -1; 
     } 
    } 
    dp[0][0] = 0; 
    // dp[i][j] denotes what's the max num of elements whose xor = j using the first i elements 
    for(i=1; i<=n; i++){ 
     for(j=0; j<=1000; j++){ 
      if(dp[i-1][j] != -1){ 
       // if j was possible using i-1 elements the using a[i] (a[i]^j) can be made using i elements 
       dp[i][j^a[i]] = max(dp[i][j^a[i]], dp[i-1][j]+1); 
      } 
      dp[i][j] = max(dp[i][j], dp[i-1][j]); 
      if(dp[i][j] != -1){ 
       ans[j] = max(ans[j], dp[i][j]); 
      } 
     } 
    } 
    for(i=0;i<=m;i++){ 
     printf("%d\n", ans[i]); 
    } 
    return 0; 
} 

vérifier la sortie à http://ideone.com/QuICHN