首页 > 代码库 > DAG上动态规划
DAG上动态规划
很多动态规划问题都可以转化为DAG上的最长路，最短路，或路径计数问题。
硬币问题：
有N中硬币，面值分别为v1,v2,v3,……vn，每种都无穷多，给定非负整数S，可以选用多少个硬币，使他们的总和恰好为S。输出硬币数目的最小值和最大值。
解：每种面值看作一个点，表示：还需要凑足的面值。则开始状态为S，目标状态为0；若当前状态为i，当使用硬币j后，状态转为i-v[j].
代码说明好了。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <cmath> 6 #include <string> 7 #include <vector> 8 #include <set> 9 #include <map>10 #include <queue>11 #include <stack>12 using namespace std;13 const int INF = 0x7fffffff;14 const double EXP = 1e-8;15 const int MS = 100005;16 int minv[MS], maxv[MS];17 int V[MS];18 int main()19 {20 fill(minv, minv + MS, INF);21 fill(maxv, maxv + MS, -INF);22 minv[0] = maxv[0] = 0;23 int N, S;24 cin >> N >> S;25 for (int i = 1; i <= N; i++)26 cin >> V[i];27 28 for (int i = 1; i <= S; i++)29 for (int j = 1; j <=N;j++)30 if (i >= V[j])31 {32 minv[i] = min(minv[i], minv[i - V[j]] + 1);33 maxv[i] = max(maxv[i], maxv[i - V[j]] + 1);34 }35 cout << minv[S] << " " << maxv[S] << endl;36 return 0;37 }
输出字典序最小的方案：
1 void print_ans(int *d, int s) 2 { 3 for (int i = 1; i <= n;i++) 4 if (s >= v[i] && d[s] == d[s - v[i]] + 1) 5 { 6 cout << i << " "; 7 print_ans(d, s - v[i]); 8 break; 9 }10 }11 print_ans(minv, S);12 cout << endl;13 print_ans(maxv, S);
另一种方法求字典序最小的方案。
用min_coin[i]来记录状态为i时，最小的j，满足d[j]+1=d[i];
code:
1 for (int i = 1; i <= S; i++) 2 for (int j = 1; j <= n; j++) 3 { 4 if (i > =v[j]) 5 { 6 if (minv[i] > minv[i - v[j]] + 1) //如果j从大到小 则>= 7 { 8 minv[i] = minv[i - v[j]] + 1; 9 min_coin[i] = j;10 }11 if (maxv[i] < maxv[i - v[j]] + 1) //如果j从大到小，则<=12 {13 maxv[i] = maxv[i - v[j]] + 1;14 max_coin[i] = j;15 }16 }17 }18 void print_ans(int *d, int S)19 {20 while (S)21 {22 cout << d[S] << " ";23 s -= v[d[s]];24 }25 }26 print_ans(min_coin, S);27 cout << endl;28 print_ans(max_coin, S);
问题二：矩形嵌套。
矩形的长宽为a,b；设一个矩形的长宽为a,b,另一个矩形长宽为c,d；当a<c&&b<d 或 b<c&&a<d时，两个矩形可以嵌套。
现在给出N个矩形，嵌套组合为第一个嵌套在第二个，第二个可以嵌套在第三个，第三个可以嵌套在第四个，……。
求数量多的嵌套组合的个数。
解：DAG 法。每个矩形抽象为一个点，当矩形a可以嵌套在矩形b时，我们在a,b之间连一条边。那么问题转化为求DAG上的最长路径。
设d[i]为从节点i出发的最长路径，则有d[i]=max(d[j]+1), (i,j)是一条边。
1 //记忆化搜索 2 int d[MS]; 3 int dp(int i) 4 { 5 int &ans = d[i]; 6 if (ans > 0) 7 return ans; 8 ans = 1; 9 for (int j = 1; j <= n; j++)10 if (G[i][j])11 ans = max(ans, dp(j)+ 1);12 return ans;13 }
输出字典序最小的方案：
1 void print_ans(int i) // d[i]==max && i is smallest 2 { 3 cout << i << " "; 4 for (int j = 1; j <= n; j++) 5 { 6 if (G[i][j] && d[i] == d[j] + 1) 7 { 8 print_ans(j); 9 break;10 }11 }12 }
DAG上动态规划
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。