ACM/计算机基础算法|【白话算法】如何根据动态规划数组求得最佳策略

我们知道,我们可以使用二维数组求得一个DP问题的最佳值,但是并没有求得其最佳方案。
【ACM/计算机基础算法|【白话算法】如何根据动态规划数组求得最佳策略】以背包问题为例,如何根据已经求得的二维数组 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] 两个状态相关。
【规则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】使用一个临时变量记录当前最佳值。


这里初始化为 intbestV= 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的无后效性】
还有,对于一行元素来说,如果这行对应的步骤已经被找到,那么这行其他列就不要再考虑了,直接 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被选中。




    推荐阅读