Problem 624 CD，背包問題

此題為一題背包問題，參考蔡宗翰譯的「演算法--使用C++虛擬碼」書中(碁峯資訊，2004年)，第五章「回溯演算法」的方式，很快就可以完成。其實這本書老師之前也有推薦我看，但我沒有注意聽到他說這件事情，而我最近才買了這本書，講解的蠻清楚的。我推薦大家可以看看這本書。

首先宣告三個整數陣列 eTime 記錄每一個 CD 的時間，bestTime 記錄最大時間 CD 的 true/false，includeTime 為記錄臨時的最大時間。在宣告三個變數 totalTime 為限制時間， index 為 CD 片數， maxTime 為最大時間。接著寫一函式 knapsack(int i, int time) 利用回溯演算法解決 0-1背包問題。C 語言程式碼如下：

int totalTime, index, maxTime;
int eTime[21], bestTime[21], includeTime[21];

void knapsack(int i, int time)
{
    int j;
    if (i <= index ) 
    {
        if (time <= totalTime && time > maxTime)
        {
            maxTime = time;
            for (j = 0; j < index; j ++)
                bestTime[j] = includeTime[j];
        }
        includeTime[i] = 1;
        knapsack(i + 1, time + eTime[i]);
        includeTime[i] = 0;
        knapsack(i + 1, time );
    }
}

最後，在主程式要如此呼叫：

for (i = 0; i < 21; i ++)
    eTime[i] = 0, bestTime[i] = 0, includeTime[i] = 0;  
for (i = 0; i < index; i ++)
    scanf("%d", &eTime[i]);
maxTime = 0;
knapsack(0, 0);
for (i = 0; i < index; i ++)
    if (bestTime[i]) printf("%d ", eTime[i]);
printf("sum:%d\n", maxTime);

By David.K

p624題目連結
回ACM題庫目錄
回首頁