アルゴリズム鉄筋切断問題 (動的計画法分割統治法)

この記事は Google 翻訳を使用して処理されました

問題の説明

ある会社が長い鉄棒を購入し、それを切断して販売します。鉄筋を切断するコストはごくわずかで、鉄筋の長さはインチです。価格表 $p$ が与えられます。ここで、 $p_{i}(i=1,2,\cdots,m)$ は長さ $i$ インチの鉄棒の価格を表します。今、売上収益を最大化するカット計画を見つける必要があります。

問題分析

長い鋼棒の長さが $n$ インチで、最適な切断計画の左端の切断セグメントの長さが $i$ インチであると仮定して、残りの鋼棒の長さに対する最適な切断計画を解き続けます。 $m-1$ インチ。すべての可能な $i$ を考慮すると、最大の利益 $r_{n}$ に対応する伐採計画が最適な伐採計画となります。 $r_{n}$ の再帰定義は次のようになる。

$$ r_{n}=max_{1\le i \le n}(p_{i}+r_{n-i}) $$

C コード

この問題には2つの解決策があります

(1) 分割統治法（上から下まで）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


int Top_Down_Cut_Rod(int p[], int n){
    int r=0; // 最大値
    int i;
    
    if(n==0){
        retrun 0;
    }
    
    for(i=1; i<=n; i++){
        int tmp = p[i]+Top_Down_Cut_Rod(p, n-i);
        r = (r>=tmp) ? r : tmp;
    }
    
    return r;
}

時間計算量 $O(2^{n})$

(2) 動的計画法（下から上まで）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


int Bottom_Up_Cut_Rod(int p[], int n, int *s){
    // *s:部分問題の最適な切断方法
    int r[n+1]; // 部分問題の最適値
    r[0]=0;
    
    for(int j=1; j<=n; j++){
        int tmp=0;
        for(int i=1; i<=j; i++){
            if(p[i]+r[j-1] > tmp){
                tmp = p[i]+r[j-i];
                s[j]=i;
            }
        }
        r[i]=tmp;
    }
    
    return r[n];
}

時間計算量 $O(n^{2})$

その他のコンテンツ

検索プロセス中に、既存の記事を見つけました：【基础算法】动态规划详解——钢条切割