1

I've been working on a program for my Algorithm Analysis class where I have to solve the Knapsack problem with Brute Force, greedy, dynamic, and branch and bound strategies. Everything works perfectly when I run it in Visual Studio 2012, but if I compile with gcc and run it on the command line, I get a different result:

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

The same number always shows up, "1599229779." Notice that the output is only messed up the first time the Dynamic algorithm is run.

Here is my code:

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

Just a bit of explanation. I was having trouble with the memory consumption of this algorithm because I have to run it for a set of 10,000 items. I realized that I didn't need to store the whole table, because I only ever looked at the previous column. I actually figured out that you only need to store the current row and x+1 additional values, where x is the weight of the current itemType. It brought the memory required from (itemsLength+1) * (maxCapacity+1) elements to 2*(maxCapacity+1) and possibly (maxCapacity+1) + (x+1) (although I don't need to optimize it that much).

Also, I used printf("%d", answer.maxValue); in this function, and it still came out as "1599229779." Can anyone help me figure out what is going on? Thanks.

4

1 回答 1

2

不能确定这是导致它的原因，但是

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 不为零，则可以解释差异。

于 2013-04-30T14:32:00.480 回答