最大借書量問題

問題描述(注：該題目來自作者改編)

假設某圖書館成立10周年，為回饋VIP會員使用者，設計了一個優惠活動：從紀念日起的連續的N天，VIP使用者每天可免費借一定數量（由圖書館系統随機生成[1...M]之間的随機數）的書籍。同時，圖書館還有一個規定，如果某使用者在第i天享受了借書優惠，那麼在第i+1天不能再享受，至少要在第i+2天才能繼續享受此優惠活動。

以N=7，M=10為例，某VIP使用者抽到的一張優惠卡，主要資訊如下：

則該使用者在第一、四、七這三天去借書可以接到獲得最大的借書量，為23本。

分析：

對于圖書館規定的不能在相鄰兩天借書，實際上等價于如下的限定條件：如果想在第i天借書，那麼在第i-1天(或有)不能借書；同時，在第i+1天(或有)也不能借書。

分析其是否具有最優子結構性質，考慮問題規模為n的最大借書量C(n)，如果在第n天不借書，必然是因為在第n-1天借了書，那麼C(n)必然等于C(n-1)；如果在第n天借書，那麼C(n)必然等于C(n-2)加上第n天的免費借書量，最後C(n)隻需要取這兩種情況的最大值即可。第n天借與不借就是一個0-1決策問題，決策後，原問題的解可由子問題C(n-1)或者C(n-2)求解得到。

很容易得到該問題的遞推關系（或者說所謂的狀态轉移方程）：

算法實作：

package agdp;
public class Books {
    public static int getMostBooks(int[] b) {//為友善計算，b數組的首項b[0]用0填充，無實際意義
        int length = b.length;
        if(length == 1){return 0;}
        int[] aux = new int[length];//輔助數組，存儲子問題的解
        aux[1] = b[1];
        for (int i = 2; i < length; i++) {
            aux[i] = Math.max(aux[i-2]+b[i], aux[i-1]);//對應的在第i天借書或者不借書
        }
        return aux[length-1];
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] ary = {0,5,1,2,10,6,2,8};
        int result = getMostBooks(ary);
        System.out.println(result);
    }
}