Visual Studio를 사용하지 않을 때 예기치 않은 값이 출력되었습니다.

Question

저는 Brute Force, greedy, dynamic 및 branch and bound 전략을 사용하여 Knapsack problem을 해결해야하는 Algorithm Analysis 클래스 용 프로그램을 작성했습니다. 모든 것은 내가 비주얼 스튜디오 2012에서 실행할 때 완벽하게 작동하지만 gcc가 컴파일 및 명령 줄에서 실행하면, 나는 다른 결과를 얻을 :

비주얼 스튜디오 :

+-------------------------------------------------------------------------------+ 
| 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 | 
+---------------+---------------+---------------+---------------+---------------+ 

명령 :

를

+-------------------------------------------------------------------------------+ 
| 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"). 동적 알고리즘이 처음 실행될 때 출력이 엉망입니다. 설명의

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"로 나타났습니다. 아무도 내가 무슨 일이 일어나고 있는지 알아낼 수 있습니까? 감사. 그 비주얼 스튜디오와 함께 항상 0 인 경우

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 

: 당신이 table[1][maxCapacity]가 초기화되지 않은 떠나, 그러나 잠재적으로 사용

Answer 1

그게 원인이 무엇인지 확인 할 수 없지만

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

, 그러나 0이 아닌 gcc는 차이점을 설명 할 수 있습니다.