about 1 year ago

動態規劃法Dynamic programming ; DP,它與分治法很像,都是將大問題分割成小問題,而它和分治法不同的地方在於,它會將處理過的子問題解答,將它記憶起來,為了避免重複的計算。

費波那西數列

最簡單說明動態規畫法的問題就是費波那西數列,它的定義如下。

F0 = 0

F1 = 1

Fn = Fn-1 + Fn-2

也就是說F2所代表的意思為F2 = F1 + F0,也就等於F2 = 1 + 0

我們直接來看程式碼,首先先看沒有用cache的費波那西數列。非常的簡單就只用遞迴來計算每個數列的值。

function fib (n){
    if(n<=1){
        return n;
    }
    return fib(n-1)+fib(n-2);
}

我們這邊使用個例子,來說明它的計算流程,我們執行fib(5),然後我們直接看下面這張圖來了解它的過程,首先是項點fib(5),它就是由fib(4)、fib(3)組成,然後再將之分解,就會如下圖的結果。其中我們有用綠色底來上色的地方,它就代表我們有重複的數字,像fib(2)就被計算了3次,所以上面這個演算法事實上做了很多重複的事情。

而接下來,我們就將它改良一下,也就是用動態規畫法的概念下修改而成,它每次計算過一個數字後,就會先存起來,然後有需要時,就在將它拿出來。

程式碼如下,它會將每個有計算過的數列儲放在記憶體內,有用到它時,就將它拿出來用。
下面就是簡單的使用動態規畫法概念實作的費波南西數列。

//有用Cache
var memo = [];
var count = 0;
var fib_cache = function(n){
    if(n <=1){
        return n;
    }

    if( typeof memo[n] !== 'undefined'){
        return memo[n];
    }else{
        memo[n] = fib_cache(n-1) + fib_cache(n-2);
        return memo[n];
    }
}

背包問題(Knapsack Problem)

這個問題的定義如下。

假設一個背包最多放10公斤的物品,要如選擇那些物品,才可以使背包的總價值最高呢?

這個問題我們事實上有很多解法,我們也可以用之前學的貪婪法來解,但我們這篇文章將要用動態規畫法來解決這問題。

要解決這個問題,我們的演算法邏輯如下。

  • 當物品重量大於限制重量時,該物品不放入,進行下個物品的比較。
  • 當物品重量小於限制重量時,考慮兩種狀況 (1) 將該商品放入後的情況 (2) 不將該商品放入後的情況。再取兩者間最大的價值。

我們簡單的用例子來說明一下。

假設可選擇物品如下。並且限重量為3

物品 重量 價值
A 2KG $3
B 3KG $2

然後我們看看下圖的執行流程,首先我們先看最上面長方形,先不要看紅色的數字,先看(3),這代表這限重量,就是我們最多可以選擇的產品,然後我們會開始跑上面有提到的演算法邏輯的流程。

注意在開始前,先不要看紅紅的方塊

首先我們會先將產品 A ,拿來決定要不要選擇,產品A重量(2)小於限制重量3,可以選擇,但要不要選呢 ? 我們要考慮兩種狀況的後果 (1) 不選擇產品 A (2) 選擇產品 A ,接下來,下圖左邊的分支,就是如果選擇第一種情況會如何。

我們先來看不選擇產品A的情況,因為它有沒有拿產品A,所以限重還是一樣(3),接下來這邊也要考慮兩種情況 (1) 不選擇產品 B (2) 選擇產品 B,由於後面沒有可選擇,所以就不需要在往下深入,直接在這層決定要選B,還是不選B ; 因為不選擇產品B總價值為0而選擇產品B的總價值為2因此,這層我們選擇產品B,也就是左邊不選擇產品A上面紅色塊塊的價值

然後我們在來看右手邊,一開始選擇產品A這分支,因為它選擇了A,所以限重量只剩(1),所以這邊我們不沒辦法在選B,所以這層的總價值為3

最後我們在來看決定要選擇 A還是選擇B,上述的流程都已經計算出這兩個選項的結果,因此我們選擇選擇產品A這個結果(3>2)

接下來我們來實作程式碼。

debugger;
var items = [{
    w: 2,
    v: 3
}, {
    w: 1,
    v: 2
}, {
    w: 3,
    v: 4
}, {
    w: 2,
    v: 2
}];

function Array2DVar(x, y) { // 定義二維陣列原型
    this.length = x;
    this.x = x; // x 維度長度
    this.y = y; // y 維度長度
    for (var i = 0; i < this.length; i++) // 建立個元素陣列
        this[i] = new Array(y); // this 代表物件本身
}
var temp = new Array2DVar(5,5);

function dpProcess(items, index, weight) {
    if (temp[index][weight] != null) {
        return temp[index][weight];
    }

    var result = 0;
    if (items.length == index) {
        result = 0;
    } else if (items[index].w > weight) {
        result = dpProcess(items, index + 1, weight);
    } else {
        result = Math.max(dpProcess(items, index + 1, weight), dpProcess(items, index + 1, weight - items[index].w) + items[index].v);
    }

    temp[index][weight] = result;
    return result;
}

console.log(dpProcess(items, 0, 5));

其中下面這段程式碼,是要產生一個矩陣,用來存放我們曾經計算過的值,當然也不一定要用矩陣,只要可以存放就好,至於為什麼這裡要用矩陣等等會說明。

function Array2DVar(x, y) { // 定義二維陣列原型
    this.length = x;
    this.x = x; // x 維度長度
    this.y = y; // y 維度長度
    for (var i = 0; i < this.length; i++) // 建立個元素陣列
        this[i] = new Array(y); // this 代表物件本身
}
var temp = new Array2DVar(5,5);

然後下面這段程式碼是判斷,如果有已經計算過的值,則直接從記憶體取出。

if (temp[index][weight] != null) {
    return temp[index][weight];
}

接下來這段是重點,它有三個區塊,首先第一個區塊,當items.length == index時,也就代表這,它已經沒有item可以繼續選擇下去了,再來第二個區塊,這塊是在說明如果某產品的重量大於剩於限重量,則往下一個產品繼續選擇,再來最後一個區塊就是我們上面所提到的過程,如下,它會將狀況分成兩種,然後再深入的去選擇。

當物品重量小於限制重量時,考慮兩種狀況 (1) 將該商品放入後的情況 (2) 不將該商品放入後的情況。再取兩者間最大的價值。

if (items.length == index) {
    result = 0;
} else if (items[index].w > weight) {
    result = dpProcess(items, index + 1, weight);
} else {
    result = Math.max(dpProcess(items, index + 1, weight), dpProcess(items, index + 1, weight - items[index].w) + items[index].v);
}
← 演算法策略---分治法 搜尋之二元搜尋法 (binary search) →
 
comments powered by Disqus