求解动态规划法拾取杂物问题（c语言）

显示全部楼层 · 2011-3-17 11:25:51

给定一个二维数组a[m][n]，任意a[j]上有不同给定数目的杂物。起点a[0][0]，要求只能向前不能后退（即i，j只能），要求用动态规划的算法求出拾取杂物最多的行进路线
不要求给出具体代码，只说说大概的求解思路就好（尤其是子问题的推导……）

千问 · 2011-3-17 11:25:51

<pre id=\"best-answer-content\" class=\"reply-text mb10\">代码在百度表示太混乱了，我说说我的做法吧
对于每个节点啊a[j]，它必定来自a[i-1][j]或a[j-1]，那么对于每个节点只要设一个同样大的数组的b[j]节点记录max{b[i-1][j],b[j-1]} a[j]
那么核心算法可以这样表示
for(i=1;i=k;i)
{
for(j=1;j=k;j)
{
if(b[i-1][j][0]b[j-1][0])

{

b[j][0]=b[i-1][j][0] a[j];

b[j][1]=0;
//表示选择上面路径
}
else
{

b[j][0]=b[j-1][0] a[j];

b[j][1]=1;
//表示选择右边路径
}
}
}
还有说明，把数组设大点，把b[0][0]和b[0][0]都设为0就可以节省判断边缘的时间
这样最后的b[i-1][j-1][0]一定就是最大值了
然后从b[i-1][j-1][1]一路回溯到起点就能找出路径了