動的計画---01リュックサックと記憶化検索

ダイナミックプランニングは効率的なアルゴリズムです.数学とコンピュータの科学の中で、1种の复雑な问题のをいくつかの简単な小さい问题の思想に分けます---分けて治します.したがって,動的計画を用いる場合,元の問題は重複するサブ問題でなければならない.動的計画を用いて設計されたアルゴリズムは,計算されたサブ問題を繰り返し計算しないため,一般的な素朴なアルゴリズムよりもずっと効率的である.動的計画は「記憶化検索」とも呼ばれるからだ.
01リュックサックはダイナミックプランニングの最も古典的な例であり、最も簡単な例でもある.まず01リュックサックを見てみましょう.

  (01  )：
         n         Wi Vi   。              W   ，                。

これが01リュックと呼ばれる問題です.動的計画を学習する前に,この問題の最初の反応がdfsで検索されるのを見た.では、まずこの方法を使って01リュックサックの問題を解きます.

//n,W      
int W, n;
//w[i] v[i]    Wi,Vi
int w[MAXN], v[MAXN];
//  i            j   
int dfs(int i, int j){
    int res;
    //        
    if(i == n) res = 0;
    //     i   
    else if(j < w[i]) res = dfs(i+1, j);
    //         ，       
    else res = max(dfs(i+1, j), dfs(i+1, j-w[i])+v[i]);
    return res;
}

一見dfsでこの問題を解決できるように見えますが、それにはダイナミックな計画があります.しかし、時間の複雑さをよく分析すると、それぞれの状態は2つの可能性を選択するか、選択しないかを使用します.従って,dfsを用いた時間的複雑度はO(2^n)であることが分かった.明らかにこの方法は良い方法ではありません.この時間は複雑すぎるからです.時間の複雑さがこのように高い原因は繰返し計算であることを注意深く研究した.複雑さがこんなに高い原因を見つけた以上、計算を繰り返す回数を減らす方法を考えることができます.よく分析すると,2次元配列を用いて検索毎の答えを記録することで,繰返し計算を回避できることが容易に考えられる.

//n,W      
int W, n;
//w[i] v[i]    Wi,Vi
int w[MAXN], v[MAXN];
//          
//   dp    ，    -1
int dp[MAXN][MAXN];
//  i            j   
int dfs(int i, int j){
    if(dp[i][j] >= 0) return dp[i][j];
    int res;
    //        
    if(i == n) res = 0;
    //     i   
    else if(j < w[i]) res = dfs(i+1, j);
    //         ，       
    else res = max(dfs(i+1, j), dfs(i+1, j-w[i])+v[i]);
    return res;
}

このような小さなテクニックは、記憶化検索と呼ばれています.私たちは小さな変化だけでその時間の複雑さをO(nW)に低下させた.
よく分析すると、もっと簡単な書き方があることがわかります.

//dp[i+1][j]     i           j    ，        
void solve(){
    //         ，        0
    for(int j = 0; j <= W; j++) dp[0][j] = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j <= W; j++){
            if(j < w[i]) dp[i+1][j] = dp[i][j];
            else dp[i+1][j] = max(dp[i+1], dp[j-w[i]]+v[i]);
        }
    }
}

繰返し方程式を用いて直接解く方法をdpと呼ぶ.彼の選択のたびに、動的な計算が最も優れているからだ.もちろん彼は局所的に最適ではないかもしれないが,全体的に最適解に違いない.これが彼と貪欲アルゴリズムの最大の違いであり、貪欲アルゴリズムは、毎回最適であるが、全体が必ずしも最適ではない.練習問題を添付します.
hdu2602Bone Collector