0

私にはパーティションの問題のように見える問題を解決しています:私は一連の整数を持っており、それらの合計がすべての整数の合計のちょうど半分です。

動的計画法で解決しようとしていますが、私の解決策はテストではまだ遅すぎます (2/10 テストしかパスできず、残りは遅すぎます)。手伝ってくれてありがとう。

私のコード:

void split(std::vector<int> seq, int sum, FILE * output){
  int n = seq.size() + 1;
  int m = sum + 1;
  bool** matrix = (bool**)malloc(m*sizeof(bool*));
  for(int i = 0;i<m;i++){
    matrix[i] = (bool*)malloc(n*sizeof(bool));
  }


  for(int i=1;i<=m-1;i++){
    matrix[0][i]=false;
  }
  for(int i=0;i<=n-1;i++){
    matrix[i][0]=true;
  }

  for(int i=1;i<=n-1;i++){
    for(int j=1;j<=m-1;j++){
      matrix[i][j] = matrix[i-1][j];
      if(matrix[i][j]==false && j>=seq[i-1])
    matrix[i][j] = matrix[i][j] || matrix[i-1][j-seq[i-1]];
    }
  }

  if(matrix[n-1][m-1]){
    int row = n-1;
    int column = m-1;

    while((row > 1) && (column > 0)){
      while(matrix[row-1][column]){row--;}
      fprintf(output, "%i ", row);
      column = column - seq[row-1];
    }
  }
  else{
    fprintf(output, "no");
  }
}
4

1 に答える 1

1

別のアプローチが許可されている場合は、二分探索木を使用して試すことができます。O(n log n)時間で終了する必要があります。ここで、 nはシーケンスのサイズです。

于 2015-12-12T22:10:23.940 に答える