演算法 - 背包問題

背包問題在演算法中為一經典題型，是一種最佳化的問題，而解決最佳化的問題，就需要用到「動態規劃」來解決，它是利用遞迴特性來拼湊出最佳解答。

以下就用 ACM 624 作為範例題目( 中文翻譯 ACM 624 )，提供解法並且解釋它是如何解決問題。

input:
5 3 1 3 4
10 4 9 8 4 2
20 4 10 5 7 4
90 8 10 23 1 2 3 4 5 7
45 8 4 10 44 43 12 9 8 2

output:
1 4 sum:5
8 2 sum:10
10 5 4 sum:19
10 23 1 2 3 4 5 7 sum:55
4 10 12 9 8 2 sum:45

不過這裡將題目改一改，不是 CD 的問題，將 CD 改為背包，而每首歌的時間長度改為物品的公斤重，在背包最大限制重量下，最多能拿幾公斤。

以下為 C# 程式碼，首先需要宣告幾個全域變數：

static int[] item_kg_array; // 每件物品的公斤重
static bool[] record_item_isTake_array; // 紀錄臨時物品是否拿取
static bool[] best_item_isTake_array; // 紀錄最佳物品是否拿取
static int max_kg; // 背包公斤限制
static int item_count; // 物品數量
static int record_max_kg; // 紀錄目前最大公斤數

在程式開頭，讀取相關資料：

string line = Console.ReadLine();
string [] value = line.Split(new string[]{" "}, 
    StringSplitOptions.RemoveEmptyEntries );

max_kg = Convert.ToInt32(value[0]);
item_count = Convert.ToInt32(value[1]);

item_kg_array = new int[item_count];
record_item_isTake_array = new bool[item_count];
best_item_isTake_array = new bool[item_count];

for (int i = 2; i < item_count + 2; i++)
    item_kg_array[i - 2] = Convert.ToInt32(value[i]);

record_max_kg = 0;

接著就是重點程式碼，以下程式碼為一函式，函式傳入索引 index 與目前公斤重 now_kg，函式一開始就先判斷 now_kg 是否大於目前最大公斤重 record_max_kg 且 now_kg 小於背包公斤限制 max_kg，如果條件成立，則紀錄 record_max_kg 為 now_kg 且紀錄最佳拿取方式 best_item_isTake_array 為 record_item_isTake_array。
再來判斷 index 使否小於物品數量 item_count，如條件成立，則先將目前索引是否拿取設置成 true 後再次呼叫自己傳入索引值加 1 及目前公斤數加上物品在索引值位置的公斤重兩數，如不成立，將目前索引是否拿取設置成 false 後再次呼叫自己傳入索引值加 1 及目前公斤數。如此一來，程式就會像「二元樹」一樣，依照 index 索引值分別來展開拿與不拿此物品的樹，而答案就會呼之欲出了。

static void knapsack(int index, int now_kg)
{
    if (now_kg <= max_kg && now_kg > record_max_kg)
    {
        record_max_kg = now_kg;
        for (int j = 0; j < index; j++)
            best_item_isTake_array[j] = record_item_isTake_array[j];
    }
    if (index < item_count)
    {
        record_item_isTake_array[index] = true;
        knapsack(index + 1, now_kg + item_kg_array[index]);
        record_item_isTake_array[index] = false;
        knapsack(index + 1, now_kg);
    }
}

最後在主程式最後呼叫並且印出：

knapsack(0, 0);
for (int i = 0; i < item_count; i++)
    if (best_item_isTake_array[i]) Console.Write("{0} ", item_kg_array[i]);
Console.WriteLine("sum:{0}", record_max_kg);

回首頁