动态规划实现货郎担问题.doc

#include #include using namespace std ; typedef list LISTINT; LISTINT listAnother; LISTINT list_result; int d44=-1,10,15,20,5,-1,9,10,6,13,-1,12,8,8,9,-1; /路径权值 int matrix_length=4; int getPath(int n,LISTINT list_org) LISTINT:iterator i; int minValue; if(n=1) i=list_org.begin(); minValue= d*i-10; if(list_org.size()=matrix_length-1) list_result=list_org; else int temp; i=list_org.begin(); temp=*i; list_org.erase(i); i=list_org.begin(); minValue=dtemp-1*(i)-1+getPath(n-1,list_org); if(list_org.size()=matrix_length-1) list_result=list_org; for(int j=2;jn;j+) i=list_org.begin(); for(int k=1;kj;k+) i+; int tempvalue=*i; list_org.erase(i); list_org.push_front(tempvalue); i=list_org.begin(); tempvalue=dtemp-1*(i)-1+getPath(n-1,list_org); if(tempvalueminValue) if(list_org.size()=matrix_length-1) list_result=list_org; minValue=tempvalue; return minValue; int main(int argc, char* argv) LISTINT list_org; LISTINT:iterator h; list_org.push_front(4); list_org.push_front(3); list_org.push_front(2); list_org.push_front(1); cout-货郎担问题动态规划算法-endlendl; cout路线长度的矩阵表示如下 （-1表示无限大）endl; for(int j=0;jmatrix_length;j+) coutendl; for(int k=0;kmatrix_length;k+) cout djk; coutendlendl; cout计算结果:getPath(4,list_org)endlendl; list_result.push_front(1); list_result.push_back(1); cout:; for (h = list_resu