ロッド切り出し問題

rod-cutting.png
1本の金属棒の材料から、どのぐらいを切り出して売れば利益を最大にできるか?という問題。
下の表は、金属棒の長さあたりの価格です。
長さ 1 2 3 4 5 6 7 8 9 10
価格 1 5 8 9 10 17 17 20 24 30

動的計画法の表で解く★

縦は現在何インチまで切り出し済みか?です
表の値としては、合計価格の最大値を入れていきます。
最大値、といっているのは、探索していく過程で、同じマスに着地してしまった場合、
前の値と新しく入れようとしている値を比べて、より大きい方で値を上書きする、という意味です。
最初は長さ0インチまで切り出し済み、つまり1個も切り出してない状態なので
表の★と書いてあるところからスタートです。

長さ 1 2 3 4
価格 1 5 8 9
0
1
2
3
4
まずこの初期状態から、1インチ切り出したら、表はこうなります
長さ 1 2 3 4
価格 1 5 8 9
0
1 1
2
3
4
現在の切り出し済みの長さ1,価格も1です。
このままひたすら1インチずつ金属棒を切り出していくと表はこうなります
長さ 1 2 3 4
価格 1 5 8 9
0
1 1
2 2
3 3
4 4
表のこの段階で、状態遷移図を書くとこうなります
rod.svg
次、初期状態から1を切り出したあと、2インチ切り出すパターンの探索をやってみましょう
合計金額1の状態から2インチ切り出すと、1+5=6になります
長さ 1 2 3 4
価格 1 5 8 9
0
1 1
2 2
3 3 1+5=6
4 4
この調子で2の列を埋めるようにして探索をすすめると
次は、1インチを2回切って合計金額2になった状態から2インチ切り出して、合計金額2+5=7の状態を表に埋めます
長さ 1 2 3 4
価格 1 5 8 9
0
1 1
2 2
3 3 6
4 4 2+5=7
ここまででどんな探索をしたことになってるのか、というのをグラフに表すとこのようになります
rod2.svg
次に、探索を進めていって、値が最大値で上書きされるパターンを見ていきたいと思います。
長さ 1 2 3 4
価格 1 5 8 9
0
1 1
2 2 5
3 3 6 8
4 4 7->10 9
元の値7よりも、2の長さを2回切り出して合計金額10になったほうが利益が大きいので、表の値は7から10に塗り替えます。
rod3.svg
最も利益が大きいのは、半分に割った時でした!
g.png
この方法のソースコード
public class RodCutting {
    int[][] mMemo;
    /**
     * @param price 棒の長さあたりの金額
     * @param n 切り出す前の棒の長さ
     * @return 利益の最大値を返す*/
    public int maximamEarn2DArray(int[] price,int n){
        System.out.println("n="+n);
        mMemo=new int[n+1][n+1];
        int maxval=0;
            //現在の合計長さ
            for(int h=0;h<n+1;h++){
                //次の遷移状態
                for(int w=0;w<n;w++){
                    int next_length=h+(w+1);
                    if(next_length>n){
                        continue;
                    }
                    int p=mMemo[w][h];
                    mMemo[w][next_length]=Math.max(mMemo[w][next_length],p+price[w]);
                    maxval=Math.max(maxval, mMemo[w][next_length]);
                }
            }
        return maxval;
    }
}

1次元配列にメモして解く方法

現在の切った長さの状態 0 1 2 3 4
最大収入 0 1 5 8 9 10
int[] mMaxValue;
    int[] mCutLengthSum;
    /**
     * @param price 棒の長さあたりの金額
     * @param n 切り出す前の棒の長さ
     * @return 利益の最大値を返す*/
    public int maximamEarn1DArray(int[] price,int n){
        System.out.println("n="+n);
        mMaxValue=new int[n+1];
        mCutLengthSum=new int[n+1];
        int maxval=0;
        for (int i = 0; i < n + 1; i++) {
            //次の遷移状態
            int next_length = mCutLengthSum[i] + i;
            if (next_length > n) {
                continue;
            }
            int p = mMaxValue[i];
            mMaxValue[next_length] = Math.max(mMaxValue[next_length], p + price[i]);
            maxval = Math.max(maxval, mMaxValue[next_length]);
        }
        Wikidot.print(mMaxValue);
        return maxval;
    }

サポートサイト Wikidot.com