【學習筆記】動態規劃(2) -- 以 ZeroJudge d637. 路過的鴨duck 為例

開場

在上一篇文章中，我們利用了這個網站來輔助我們了解與完成1-0背包問題，今天我們要以d637. 路過的鴨duck為例，帶來程式碼的部分！

動態規劃

在上一篇文章，我們似乎還沒好好地介紹什麼是「動態規劃」，「動態規劃」，英文為Dynamic programming，簡稱DP，是一種重要的演算法（algorithm），在利用「動態規劃」解題時，若問題可以切割成許多相對較簡單的小問題，那麼經由將小問題解決，可以組合成大問題（原問題）的解！

接下來，我們以1-0背包問題的觀念為基礎，以d637. 路過的鴨duck為例，帶出程式碼！

範例程式

#include <bits/stdc++.h>
using namespace std;
int w[10001],v[10001],dp[10001][10001];
int n;
int main(){
    while(cin>>n){
        for(int i=0;i<n;i++){
            cin>>w[i]>>v[i];
        }
        memset(dp,0,sizeof(dp));
        for(int i=0;i<n;i++){
            for(int j=0;j<=100;j++){
                if(0>j-w[i])
                   dp[i+1][j]=dp[i][j];
                else
                   dp[i+1][j]=max(dp[i][j], dp[i][j-w[i]]+v[i]);
            }
        }
        cout<<dp[n][100];
    }
    return 0;
}

解析

所以，一開始我們先定義

int w[10001],v[10001],dp[10001][10001];
int n;

這幾個變數，分別用來儲存物品重量、物品價值與我們的表格（也就是在第一篇時的那些表格），另外定義一個變數n，這樣子可以做到多行輸入。

接下來可以看見下面這段：

memset(dp,0,sizeof(dp));

這一段的意思是：我把我的dp陣列的值全部設定為0，sizeof(dp)則是指設定的數量！

for(int i=0;i<n;i++){
    for(int j=0;j<=100;j++){
	if(0>j-w[i])
    	    dp[i+1][j]=dp[i][j];
	else
    	    dp[i+1][j]=max(dp[i][j], dp[i][j-w[i]]+v[i]);
    	}
}

上面這段則是在執行動態規劃的過程，我們來一步一步地做講解：

在第11、12行有兩個for迴圈，而這2個迴圈是用於遍歷我們的陣列，這麼做是為了確認陣列內是否存在其他最優解。在迴圈裡面我們塞入了一個判斷式，而這個判斷式式什麼意思呢？

if(0>j-w[i])-else是在判斷當前背包負重能力是否小於物品重，若是，則將dp[i+1][j]移下來，若否，則在dp[i][j]與dp[i][j-w[i]]+v[i]之間取其大，為最優解。

最後再cout最終解即是解答囉！

結語

演算法需要多花時間理解與練習，還望各位多花時間在練習上！希望這篇文章對您有幫助 :D