首页 > 代码库 > 多阶段决策问题
多阶段决策问题
每做一次决策就可以得到解的一部分,当所有决策做完以后,完整的解就"浮出水面“。在回溯法中,每次决策对应于给一个结点产生新的子树,而解的生成过程对应一颗解答树,结点的层数就是下一个待填充的位置
UVA116
分析:dp[i][j]记录从(i,j)出发的最小值,本题同时还要求输出字典序最小的解,所以需要计算时记录下一列行号的最小值。
1 #include "iostream" 2 #include "cstdio" 3 #include "cstring" 4 #include "string" 5 #include "algorithm" 6 using namespace std; 7 const int maxn=100+10; 8 const int INF=1<<30; 9 int m,n; 10 int a[maxn][maxn]; 11 int dp[maxn][maxn]; 12 int Next[maxn][maxn]; 13 int main() 14 { 15 //freopen("uva116.txt","r",stdin); 16 //freopen("uva116.out","w",stdout); 17 while(cin>>m>>n) 18 { 19 for(int i=1;i<=m;i++) 20 for(int j=1;j<=n;j++) 21 cin>>a[i][j]; 22 memset(Next,0,sizeof(Next)); 23 int ans=INF,f=0; 24 for(int j=n;j>=1;j--){ 25 for(int i=1;i<=m;i++){ 26 if(j==n){ 27 dp[i][j]=a[i][j]; 28 }else{ 29 int col[3]={i-1,i,i+1}; 30 if(i==1) col[0]=m; 31 if(i==m) col[2]=1; 32 sort(col,col+3); 33 dp[i][j]=INF; 34 for(int k=0;k<3;k++){ 35 int v=dp[col[k]][j+1]+a[i][j]; 36 if(v<dp[i][j]){ 37 dp[i][j]=v; 38 Next[i][j]=col[k]; 39 } 40 } 41 } 42 if(j==1&&ans>dp[i][j]){ 43 ans=dp[i][j]; 44 f=i; 45 } 46 } 47 } 48 cout<<f; 49 for(int i=Next[f][1],j=2;j<=n;i=Next[i][j],j++) 50 cout<<" "<<i; 51 cout<<endl; 52 cout<<ans<<endl; 53 } 54 return 0; 55 }
多阶段决策问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。