绥化建设网站,苏州建网站提,中卫网站设计公司排名,企业管理考研动态规划
动态规划算法的有效性依赖于问题本身所具有的两个重要性质#xff1a;最优子结构、重叠子问题
关于动态规划算法和备忘录方法的适用条件#xff1a;
要求#xff1a; 用分治法和动态规划法分别解决最大子段和问题#xff08;第四步求最优解不需要掌握#xff…动态规划
动态规划算法的有效性依赖于问题本身所具有的两个重要性质最优子结构、重叠子问题
关于动态规划算法和备忘录方法的适用条件
要求 用分治法和动态规划法分别解决最大子段和问题第四步求最优解不需要掌握
掌握用动态规划法解决0-1背包问题
最长单调递增子序列
最长公共子序列会写出计算最长公共子序列长度的递推式即可
矩阵连乘问题
备忘录做法
signed main()
{cinn;for(int i0;in;i) for(int j0;jn;j) dp[i][j]inf;for(int i1;in;i) dp[i][i]0;for(int i1;in;i)cinrow[i]col[i];for(int i1;in;i) p[i]col[i];p[0]row[1];for(int len2;lenn;len){for(int i1;in-len1;i){int jilen-1;dp[i][j]dp[i1][j]p[i-1]*p[i]*p[j];s[i][j]i;for(int ki1;kj;k){int tmpdp[i][k]dp[k1][j]p[i-1]*p[k]*p[j];if(tmpdp[i][j]){dp[i][j]tmp;s[i][j]k;}}}}coutdp[1][n]endl;dfs(1,n);return 0;
}动态规划做法
signed main()
{cinn;for(int i0;in;i) for(int j0;jn;j) dp[i][j]inf;for(int i1;in;i) dp[i][i]0;for(int i1;in;i)cinrow[i]col[i];for(int i1;in;i) p[i]col[i];p[0]row[1];for(int len2;lenn;len){for(int i1;in-len1;i){int jilen-1;dp[i][j]dp[i][i]dp[i1][j]p[i-1]*p[i]*p[j];s[i][j]i;for(int ki1;kj;k){if(dp[i][j]dp[i][k]dp[k1][j]p[i-1]*p[k]*p[j]){dp[i][j]dp[i][k]dp[k1][j]p[i-1]*p[k]*p[j];s[i][j]k;}}}}coutdp[1][n]endl;print(1,n);return 0;
}最大子段和问题
法一
#include bits/stdc.h
#define endl \n
#define int long long
using namespace std;
const int N1e35;
const int inf1e18;
int n,a[N],dp[N];signed main()
{cinn;for(int i1;in;i) cina[i];int ans0;for(int i1;in;i){dp[i]max(dp[i-1]a[i],0ll);ansmax(ans,dp[i]);}coutansendl;return 0;
}
/*
7
-2 11 -4 13 -5 -2 -100
*/
法二
signed main()
{cinn;for(int i1;in;i) cina[i];int ans0,b0;for(int i1;in;i){if(b0)ba[i];elseba[i];ansmax(ans,b);}coutansendl;return 0;
}法三
#include bits/stdc.h
#define endl \n
#define int long long
using namespace std;
const int N1e35;
const int inf1e18;
int n,a[N],dp[N];
int dfs(int l,int r)
{if(lr)return a[l]0?a[l]:0;int sum0,mid(lr)/2;int leftdfs(l,mid);int rightdfs(mid1,r);int s10,s20,tmp0;for(int imid;il;i--){tmpa[i];if(s1tmp) s1tmp;}tmp0;for(int imid1;ir;i){tmpa[i];if(s2tmp) s2tmp;}sums1s2;if(leftsum) sumleft;if(rightsum) sumright;return sum;
}
signed main()
{cinn;for(int i1;in;i) cina[i];coutdfs(1,n)endl;return 0;
}
/*
7
-2 11 -4 13 -5 -2 100
*/
01背包问题
int n,m,f[105][N],dp[N];void fun1()
{for(int i1;in;i) //物品i{for(int j1;jm;j) //容量j{if(jw[i])f[i][j]f[i-1][j];else f[i][j]max(f[i-1][j],f[i-1][j-w[i]]c[i]);}}coutf[n][m]endl;
}
void fun2() //逆序更新
{for(int i1;in;i){for(int jm;jw[i];j--)dp[j]max(dp[j],dp[j-w[i]]c[i]);}
}
最长单调递增子序列
for(int i1;in;i) cina[i],dp[i]1;for(int i2;in;i){for(int j1;ji;j){if(a[j]a[i])dp[i]max(dp[i],dp[j]1);}}coutdp[n]endl;最长公共子序列
{cins1s2;len1s1.length(),len2s2.length();s1 s1,s2 s2;for(int i1;ilen1;i){for(int j1;jlen2;j){if(s1[i]s2[j]) dp[i][j]dp[i-1][j-1]1,s[i][j]1;else{if(dp[i-1][j]dp[i][j-1]){dp[i][j]dp[i-1][j];s[i][j]2;//上面}elsedp[i][j]dp[i][j-1];s[i][j]3;}}}coutdp[len1][len2]endl;return 0;
}贪心算法
适合于贪心算法求解的问题具有贪心选择性质、最优子结构性质 贪心算法可以获取到问题的局部最优解不一定能获取到全局最优解 掌握使用贪心算法解决活动安排问题、背包问题、最优装载问题件数最多、删数问题
活动安排问题
按照结束时间进行排序
int n,p[N];
struct node
{int st,ed,id;
}a[N];
bool cmp(node a,node b)
{return a.edb.ed;
}
signed main()
{cinn;for(int i1;in;i) {cina[i].sta[i].ed;a[i].idi;}sort(a1,an1,cmp);p[1]1;int ans1,tmpa[1].ed;for(int i2;in;i){if(a[i].sttmp){tmpa[i].ed;ans;p[i]1;}}coutansendl;return 0;
}背包问题
int n,p[N];
struct node
{int w,v;double d;
}a[N];
bool cmp(node a,node b)
{return a.db.d;
}
signed main()
{cinnc;for(int i1;in;i){cina[i].wa[i].v;a[i].da[i].v/a[i].w;}sort(a1,an1,cmp);int i1;double ans0;while(ina[i].wc){c-a[i].w;ansa[i].v;i;}if(in) ansc*a[i].d;coutansendl;return 0;
}最优装载问题件数最多
重量轻的先装找找重量从小到大进行排序
删数问题
找到最近下降点
#include bits/stdc.h
#define int long longusing namespace std;
const int N 7e6100;
const int mod 998244353;
int n,k;
string s;signed main()
{cinsk;ns.length();if(kn)cout0endl;else{while(k){int i;for(i0;is.length()s[i]s[i1];i);s.erase(i,1);k--;}while(s.size()1s[0]0)s.erase(0,1);coutsendl;}return 0;
}
/**/
第六章
子集树实现素数环
const int N 1e65;
int n,a[N],vis[N],ans;
int check(int a,int b)
{int sumab;for(int i2;i*isum;i)if(sum%20)return 0;return 1;
}
void dfs(int x)
{if(xn1){if(check(a[1],a[n]))ans;return;}for(int i1;in;i){if(!vis[i]check(a[x-1],i)){vis[i]1;a[x]i;dfs(x1);vis[i]0;}}
}
void solve()
{cinn;dfs(1);coutansendl;
}
signed main()
{solve();return 0;
}
排列树实现素数环
int n,a[N],vis[N],ans;
int check(int a,int b)
{int sumab;for(int i2;i*isum;i)if(sum%20)return 0;return 1;
}
void dfs(int x)
{if(xn1){if(check(a[1],a[n]))ans;return;}for(int ix;in;i){swap(a[x],a[i]);if(check(a[x-1],a[x]))dfs(x1);swap(a[x],a[i]);}
}
void solve()
{cinn;for(int i1;in;i) a[i]i;dfs(1);coutansendl;
}装载问题
#include bits/stdc.h
#define endl \n
#define int long longusing namespace std;
const int N 1e65;
const int inf1e18;
int n,c,a[N],b[N],ans[N],sum,bestcw;
void dfs(int x,int cw)
{if(xn1){if(cwbestcw){for(int i1;in;i)ans[i]b[i];bestcwcw;}return;}sum-a[x];if(cwa[x]c){b[x]1;cwa[x];dfs(x1,cw);cw-a[x];}if(cwsumbestcw){b[x]0;dfs(x1,cw);}suma[x];
}
void solve()
{cinnc;for(int i1;in;i) cina[i],suma[i];dfs(1,0);coutbestcwendl;for(int i1;in;i)coutans[i] ;coutendl;
}
signed main()
{solve();return 0;
}
01背包问题回溯贪心
剪枝规则 约束函数当选取一个物品时累计的中部不可大于背包容量C 限界函数根据物品单位重量的价值进行降序排列越靠近树根位置剪掉分枝越多从而加快搜索bound(i)定义为当前选取物品价值的和加上剩余物品的价值和根据贪心的性质剩余物品不会比贪心选取的物品方案更优若bound(i)此时最优价值则进行剪枝。
int n,c,cw,cv,bestv;
struct node
{int w,v;double d;
}a[N];
bool cmp(node a,node b)
{return a.db.d;
}
int check(int x)
{int vcv;int tmpc-cw;while(xna[x].wtmp){tmp-a[x].w;va[x].v;x;}if(xn)v1.0*tmp*a[x].w;return v;
}
void dfs(int x)
{if(xn1){bestvcv;return;}if(cwa[x].wc){cwa[x].w;cva[x].v;dfs(x1);cw-a[x].w;cv-a[x].v;}if(check(x1)bestv)dfs(x1);
}
signed main()
{cincn;for(int i1;in;i){cina[i].wa[i].v;a[i].da[i].v*1.0/a[i].w;}sort(a1,an1,cmp);dfs(1);coutbestvendl;return 0;
}
/*
50 3
10 60
30 120
20 100
*/
n皇后问题
int n,m,a[105][105],p[N],ans;
int check(int x)
{for(int i1;ix;i)if(abs(x-i)abs(p[x]-p[i])||(p[i]p[x]))return 0;return 1;
}
void dfs(int x)
{if(xn1){ans;for(int i1;in;i)coutp[i] ;coutendl;return;}for(int i1;in;i){p[x]i;if(check(x))dfs(x1);}
}
signed main()
{cinn;dfs(1);if(ans)coutansendl;elsecoutNo Solution!endl;return 0;
}
