未使用Visual Studio時出現意外值輸出

Question

我一直在爲我的算法分析類開發一個程序，在那裏我必須用Brute Force，貪婪，動態和分支定界策略來解決Knapsack problem。一切都完美的作品，當我在Visual Studio 2012中運行它，但如果我用gcc編譯，在命令行中運行它，我得到了不同的結果：

的Visual Studio：

+-------------------------------------------------------------------------------+ 
| Number of |  Processing time in seconds/Maximum benefit value  | 
|    +---------------+---------------+---------------+---------------+ 
|  items  | Brute force |  Greedy |  D.P.  | B. & B. | 
+---------------+---------------+---------------+---------------+---------------+ 
|  10  + 0/1290 + 0/1328 + 0/1290 + 0/1290 | 
+---------------+---------------+---------------+---------------+---------------+ 
|  20  + 0/3286 + 0/3295 + 0/3200 + 0/3286 | 
+---------------+---------------+---------------+---------------+---------------+ 

CMD：

+-------------------------------------------------------------------------------+ 
| Number of |  Processing time in seconds/Maximum benefit value  | 
|    +---------------+---------------+---------------+---------------+ 
|  items  | Brute force |  Greedy |  D.P.  | B. & B. | 
+---------------+---------------+---------------+---------------+---------------+ 
|  10  + 0/1290 + 0/1328 + 0/1599229779+ 0/1290 | 
+---------------+---------------+---------------+---------------+---------------+ 
|  20  + 0/3286 + 0/3295 + 0/3200 + 0/3286 | 
+---------------+---------------+---------------+---------------+---------------+ 

相同的數字總是顯示「1599229779.」請注意，輸出僅在Dynamic算法第一次運行時混亂。

這裏是我的代碼：

typedef struct{ 
    short value;  //This is the value of the item 
    short weight;  //This is the weight of the item 
    float ratio; //This is the ratio of value/weight 
} itemType; 

typedef struct{ 
    time_t startingTime; 
    time_t endingTime; 
    int maxValue; 
} result; 

result solveWithDynamic(itemType items[], int itemsLength, int maxCapacity){ 
    result answer; 
    int rowSize = 2; 
    int colSize = maxCapacity + 1; 
    int i, j; //used in loops 
    int otherColumn, thisColumn; 

    answer.startingTime = time(NULL); 

    int **table = (int**)malloc((sizeof *table) * rowSize);//[2][(MAX_ITEMS*WEIGHT_MULTIPLIER)]; 
    for(i = 0; i < rowSize; i ++) 
     table[i] = (int*)malloc((sizeof *table[i]) * colSize); 

    table[0][0] = 0; 
    table[1][0] = 0; 

    for(i = 1; i < maxCapacity; i++) table[1][i] = 0; 

    for(i = 0; i < itemsLength; i++){ 
     thisColumn = i%2; 
     otherColumn = (i+1)%2; //this is always the other column 

     for(j = 1; j < maxCapacity + 1; j++){ 
      if(items[i].weight <= j){ 
       if(items[i].value + table[otherColumn][j-items[i].weight] > table[otherColumn][j]) 
        table[thisColumn][j] = items[i].value + table[otherColumn][j-items[i].weight]; 
       else 
        table[thisColumn][j] = table[otherColumn][j]; 
      } else { 
      table[thisColumn][j] = table[thisColumn][j-1]; 
      }//end if/else 
     }//end for 
    }//end for 

    answer.maxValue = table[thisColumn][maxCapacity]; 

    answer.endingTime = time(NULL); 

    for(i = 0; i < rowSize; i ++) 
     free(table[i]); 
    free(table); 

    return answer; 
}//end solveWithDynamic 

只是有點解釋。我在這個算法的內存消耗方面遇到了問題，因爲我必須運行它以獲得一組10,000個項目。我意識到我不需要存儲整個桌子，因爲我只看過前一列。實際上我發現只需要存儲當前行和x + 1個附加值，其中x是當前itemType的權重。它將(itemsLength+1) * (maxCapacity+1)元素所需的內存帶到2*(maxCapacity+1)，可能還有(maxCapacity+1) + (x+1)（儘管我不需要優化它）。

此外，我在這個函數中使用了printf("%d", answer.maxValue);，它仍然是「1599229779」。任何人都可以幫我弄清楚發生了什麼事？謝謝。

Answer 1

不能肯定這是什麼原因造成的，但

for(i = 1; i < maxCapacity; i++) table[1][i] = 0; 

你離開table[1][maxCapacity]未初始化的，但隨後可能使用它：

for(j = 1; j < maxCapacity + 1; j++){ 
    if(items[i].weight <= j){ 
     if(items[i].value + table[otherColumn][j-items[i].weight] > table[otherColumn][j]) 
      table[thisColumn][j] = items[i].value + table[otherColumn][j-items[i].weight]; 
     else 
      table[thisColumn][j] = table[otherColumn][j]; 
    } else { 
     table[thisColumn][j] = table[thisColumn][j-1]; 
    }//end if/else 
}//end for 

如果使用Visual Studio始終爲零，但用gcc非零，這可以解釋不同之處。