【白話アルゴリズム】動的計画配列に基づいて最適なポリシーを求める方法

二次元配列を用いてDP問題の最適値を求めることができることを知っているが,その最適スキームは求められていない.
リュックサック問題を例にとると,求めた2次元配列dp[N+1][W+1]に基づいて最適な選択案を求めるにはどうすればよいのだろうか.
DPコードを見るだけで、以下のようになります.

int dpf[N+1][W+1]; //   0  
int dp_solve()
{
	for(int i=0; i

dpf[i+1][j]進とdpf[i][j]、dpf[i][j-w[i]+v[i]の2つの状態相関を見ることができる.
【ルール1】新しいステップを追加するためのキー条件を特定します.
また、dpf[i][j]に関連すると、最適価値は変化しないので、新しいステップは追加されないので、dpf[i][j]==dpf[i-1][j-w[i-1]++v[i-1]の場合を考慮するだけです.(dpfはNから,w,v配列はN−1から先)
【小結】以上は、主に最適価値を変化させる「そのステップ」を探し出す.変化しただけなので、このステップが最適戦略の一歩である可能性があることを説明する.【ルール2】DPは順方向に行われているので、最適案を求めるには逆方向から考えるべきである.
基本ループを書き出します.

for( int i=N;i>0;i++)
    for( int j=W;j>0;j++)
	

まずdpf[N][W]は必ず最適値である.
【ルール3】現在の最適値を一時変数で記録する.
ここでint bestV=dpf[N][W];
我々は、現在のdpf[i][j]が現在の最適値に等しくないことを発見した場合、考慮する必要はなく、我々が必要とする戦略の一歩ではないに違いない.
したがって,我々はサイクル毎にdpf[i][j]==bestVの場合を考慮する必要がある. 
【小結】以上の考えでは、現在の最適値がいくらであるか、リュックサックのように、この最適値から前進する戦略を探しています.例えば、リュックサックの中で、現在の最適値が7であれば、現在の状態で最適値が6のdpf[q][p]に遭遇した場合、直接無視することができます.
次に、「最適なポリシーのステップ」を探すコードを書くことができます.

int bestV=dpf[N][W];
for( int i=N;i>0;i++)
    for( int j=W;j>0;j++)
        if ( dpf[i][j] == dpf[i-1][j-w[i-1]]+v[i-1]  && bestV==dpf[i][j])  //         bestV == dpf[i-1][j-w[i-1]]+v[i-1],    
		{
		    //           ，    
		}

現在の最適なステップが見つかった後、いくつかの変数を更新する必要があります.
【ルール4】現在の最適値の更新、ステップの記録など.
bestVを、現在のステップを除いた前のすべてのステップからなるスキームが得られる価値に変更します.
ここでbestV=dpf[i-1][j-w[i-1]];
次のようにすべてのコードを書くことができます.
もちろん、0-1リュックサックの問題に対して、この戦略を探す方法を最適化することができます.
例えば、最適値を更新する場合、jの各ラウンドiの開始時の初期値を更新することもできます.理由は、「ヒント、DPの無後効性」です.
また、1行の要素について、この行に対応するステップが見つかった場合、この行の他の列は考慮せずに、直接breakすればよい. 

int bestV=dpf[N][W];
string a = "";
for( int i=N;i>0;i++)
    for( int j=W;j>0;j++)
        if ( dpf[i][j] == dpf[i-1][j-w[i-1]]+v[i-1]  && bestV==dpf[i][j])
		{
		     a = a + char(i+48); 
			 bestV = dpf[i-1][j-w[i-1]];
		}
//    ：   1345       1 3 4 5   。