网站建设宗旨怎么写,最完整的外贸流程图,私人域名可以做公司网站备案吗,仿搜狐视频网站源码贪心算法
适合于贪心算法求解的问题具有#xff1a;贪心选择性质、最优子结构性质。 贪心算法可以获取到问题的局部最优解#xff0c;不一定能获取到全局最优解。 贪心算法总是作出在当前看来最好的选择#xff1b;并且每次贪心选择都能将问题化简为一个更小的与原问题具有…贪心算法
适合于贪心算法求解的问题具有贪心选择性质、最优子结构性质。 贪心算法可以获取到问题的局部最优解不一定能获取到全局最优解。 贪心算法总是作出在当前看来最好的选择并且每次贪心选择都能将问题化简为一个更小的与原问题具有相同形式的子问题。
活动安排问题
回溯算法
应用回溯法求解时需要明确定义问题的解空间。 旅行商问题–使用排列数解决。
用约束函数在扩展结点处剪去不满足约束条件的子树 用限界函数剪去不能得到最优解的子树。
三个步骤 1.针对所给问题定义问题的解空间 2.确定易于搜索的解空间结构 3.以深度优先的方式搜索解空间并且在搜索过程中使用剪枝函数避免无效搜索。 子集树
void backtrack (int t) // 形参t为树的深度根为1
{if(tn){update(t);return;}for(int i0;i2;i){x[t]i;if(constrant(t)bound(t))backtrack(t1);}
}排列树
void backtrack (int t) // 形参t为树的深度根为1
{if(tn){update(t);return;}for(int i0;i2;i){x[t]i;if(constrant(t)bound(t))backtrack(t1);}
}素数环问题
int n,a[N],ans;
bool vis[N];
int check(int x,int y)
{int sumxy;for(int i2; i*isum; i)if(sum%i0) return 0;return 1;
}
void dfs(int x)
{if(xn1){if(check(a[n],a[1]))ans;return;}for(int i1;in;i){if(!vis[i]check(i,a[x-1])){vis[i]1;a[x]i;dfs(x1);vis[i]0;}}
}
void solve()
{cinn;dfs(1);coutansendl;
}最优装载问题
#include bits/stdc.h
#define endl \n
#define int long longusing namespace std;
const int N 7e35;
const int inf1e18;
const int mod1e97;
const double eps1e-8;
int n,c,a[N],sum,bestcw,b[N],ans[N];
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];
}
signed main()
{cinnc;for(int i1;in;i)cina[i],suma[i];dfs(1,0);coutbestcwendl;return 0;
}
/*
4 34
21 10 5 2
*/
回溯算法 实现01背包
#include bits/stdc.h
#define endl \n
#define int long longusing namespace std;
const int N 7e35;
const int inf1e18;
const int mod1e97;
const double eps1e-8;
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;
}
double check(int x)
{int tmpc-cw;double vcv;while(xna[x].wtmp)tmp-a[x].w,va[x].v,x;if(xn) v1.0*tmp*a[x].d;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;}cout1endl;sort(a1,an1,cmp);dfs(1);coutbestvendl;return 0;
}
/*
50 3
10 60
30 120
20 100
*/
n皇后问题
法一:
int n,m,a[105][105],tag[105][3],ans;
void dfs(int x)
{if(xn1){ans;return;}for(int i1;in;i){if(!tag[i][0]!tag[ix][1]!tag[30i-x][2]){tag[i][0]1;tag[ix][1]1;tag[30i-x][2]1;dfs(x1);tag[i][0]0;tag[ix][1]0;tag[30i-x][2]0;}}
}法二
#include bits/stdc.h
#define int long long
#define lowbit(x) ((x)(-x))
#define endl \n
#define lowbit(x) (x(-x))
using namespace std;
const int N 7e6100;
const int mod 998244353;
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()
{//ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinn;dfs(1);if(ans)coutansendl;elsecoutNo Solution!endl;return 0;
}
图的m着色问题
解空间的大小为m^n种
