1

私は、ブルート フォース、貪欲、動的、および分岐限定戦略を使用してナップザック問題を解決する必要があるアルゴリズム分析クラスのプログラムに取り組んできました。Visual Studio 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」と出ました。何が起こっているのかを理解するのを手伝ってくれる人はいますか? ありがとう。

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 に答える