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