下面是包含 +ve 和 -ve 数字的数组的标准最大和的代码。我认为,以下程序工作正常。机器人如何打印最佳路径? 通过保持指向最佳父级的指针,我可以轻松地向后打印路径,但如何向前打印它,最好不要保留太多额外的簿记。
#include <stdio.h>
main()
{
int array[]={5,-5,3,4,-2};
int n=5;
int i;
int maxsumendingat[n];
int parent[n];
int maxsum=-9999; // better way to code?
int optimallastindex;
maxsumendingat[0]=array[0];
for(i=1;i<n;i++)
{
if(maxsumendingat[i-1] <= 0)
{
maxsumendingat[i]=array[i];
parent[i]=i;
}
else
{
maxsumendingat[i]=array[i]+maxsumendingat[i-1]; // also keep backtracking info
parent[i]=i-1;
}
}
// now print results
for(i=0;i<n;i++)
{
if(maxsum < maxsumendingat[i])
{
maxsum=maxsumendingat[i];
optimallastindex=i;
}
}
// now print path. how to print it in fwd direction?
i=optimallastindex;
printf("%d ",array[i]);
while(parent[i]!= i)
{
printf("%d ",array[parent[i]]);
i=parent[i];
}
}
最佳答案
只需将反向路径存储在一个临时数组中,然后向后迭代该数组。
关于c - 如何在动态规划技术中从头开始打印最佳路径,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6321128/