Я решаю проблему, которая для меня выглядит как проблема с разбиением: у меня есть последовательность целых чисел, и я должен найти одно (если существует более одного решения, я должен вывести только одно) подмножество этих целых чисел, такое что их сумма ровно половина суммы всех целых чисел.
Я пытаюсь решить это с помощью динамического программирования, но мое решение все еще слишком медленно в тесте (я могу пройти только 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");
}
}
fprintf
в цикле? Кроме того, вы выделяете память и никогда не освобождаете ее. Если эта функция вызывается в цикле, вы создаете огромные утечки памяти, еслиn
иm
велики. - person PaulMcKenzie   schedule 13.12.2015while(matrix[row-1][column]){row--;}
при запуске сvector<int> v{2, 3, 5, 6}; split(v, 16);
- person karastojko   schedule 13.12.2015