当前位置: 首页 > news >正文

2021外贸网站有哪些想做推广哪个平台好

2021外贸网站有哪些,想做推广哪个平台好,网站建设报价表下载,深圳企业网站制作文章目录 一、贪心算法概述二、活动安排问题2.1 问题概述2.2 代码编写 三、背包问题3.1 问题描述3.2 代码编写 一、贪心算法概述 1. 贪心算法的定义:贪心算法是指在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以…

文章目录

  • 一、贪心算法概述
  • 二、活动安排问题
    • 2.1 问题概述
    • 2.2 代码编写
  • 三、背包问题
    • 3.1 问题描述
    • 3.2 代码编写


一、贪心算法概述

 1. 贪心算法的定义:贪心算法是指在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,只做出在某种意义上的局部最优解。

 2. 注意:贪心算法对有些问题可以快速获得整体最优解。对有些问题虽不能得到整体最优解,却可以得到近似最优解。

 3. 用贪心算法求解问题要满足以下条件:

  • 贪心选择性质:贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择来得到,即通过贪心选择来达到。
  • 最优子结构性质:一个问题的最优解包含其子问题的最优解。

 4. 贪心算法与动态规划的差异:

  • 相同:贪心算法和动态规划算法都要求问题具有最优子结构性质。
  • 不同:动态规划算法通常以自底向上的方式解各子问题;贪心算法通常以自顶往下的方式进行,每做一次贪心选择就将问题简化为规模更小的子问题。

 5. 贪心算法解题的一般步骤是:

  • 建立数学模型来描述问题。
  • 把求解的问题分成若干个子问题。
  • 对每一子问题求解,得到子问题的局部最优解。
  • 把子问题的局部最优解合成原来问题的一个解。

二、活动安排问题

2.1 问题概述

 1. 有 n n n 个需要在同一天使用同一个教室的活动: a 1 , a 2 , … , a n a_1,a_2,…,a_n a1,a2,,an。教室同一时刻只能由一个活动使用。每个活动 a i a_i ai 都有一个开始时间 s i s_i si 和结束时间 f i f_i fi。一旦被选择后,活动 a i a_i ai 就占据半开时间区间 [ s i , f i ) [s_i,f_i) [si,fi)。如果 [ s i , f i ) [s_i,f_i) [si,fi) [ s j , f j ) [s_j,f_j) [sj,fj) 互不重叠, a i a_i ai a j a_j aj 两个活动就可以被安排在这一天。该问题就是要安排这些活动,使得尽量多的活动能不冲突地举行。

 2. 可以用数学归纳法证明,我们的贪心策略应该是每次选取结束时间最早的活动。直观上也很好理解,按这种方法选择相容活动为未安排活动留下尽可能多的时间。这也是把各项活动按照结束时间单调递增排序的原因。

在这里插入图片描述

2.2 代码编写

 1. 不需要我们排序的代码:

#include<bits/stdc++.h>  
using namespace std; void activity_select(int n, int s[], int f[], int selected[])
{int j = 1; //j记录最近一次加入的活动 selected[1] = 1; //首先选择活动1 for (int i = 2; i <= n; i ++)if (s[i] >= f[j]) //如果活动i与活动j兼容,则选择活动i{  selected[i] = 1;j = i;}else{selected[i] = 0;}
}int main()
{cout<<"请输入活动的个数:"; int n;cin>>n;int s[n],f[n];  //s[i],f[i]存储活动i的开始和结束时间int selected[n];  //若活动i被选择,则selected[i]置1,否则置0cout<<"请输入活动的开始和结束时间(按照结束时间升序输入):"<<endl;for (int i = 1; i <= n; i++){cin>>s[i]>>f[i];}activity_select(n,s,f,selected);cout<<"有如下活动被选择:"<<endl;for (int i = 1; i <= n; i++){if (selected[i] == 1){cout<<i<<" "; }}	return 0;
}

 2. 需要我们排序的代码:

#include<bits/stdc++.h>
#include<iostream>
using namespace std;    struct activity //活动结构体 
{int start;int end;
};bool cmp(activity a,activity b)  //cmp参数为sort函数的排序准则,设置为按照活动的结束时间由小到大排序 
{  return a.end<b.end;  
} void activity_select(int n,int selected[],activity act[])  
{  int i=1;selected[1]=1; for(int j=2;j<=n;j++)  //从结束时间倒数第二小的活动开始遍历 {  if(act[j].start>=act[i].end)  {  i=j;   selected[j]=1; }  else{selected[j]=0;}}  
}int main()  
{cout<<"请输入活动的个数:";int n;cin>>n;int selected[n]; //若活动i被选择,则selected[i]置1,否则置0activity act[n];cout<<"请输入活动的开始和结束时间(按照结束时间升序输入):"<<endl;   for(int i=1;i<=n;i++){cin>>act[i].start>>act[i].end;}act[0].start=-1;act[0].end=-1;sort(act+1,act+n+1,cmp); //act+1表示第2个元素(i=1,第1个活动) activity_select(n,selected,act);  cout<<"有如下活动被选择:"<<endl;for (int i=1; i<=n; i++){if (selected[i]==1){cout<<i<<" "; }}	return 0;
}  

三、背包问题

3.1 问题描述

 1. 假设有 n n n 件物品,每件物品 i i i 对应价值为 v i v_i vi,重量 w i w_i wi。背包只能装入重量为 m m m 的物品。每件物品只能拿 1 1 1 件,可以分割。问题是怎样放使得背包装入的物品价值最大?

 2. 贪心策略:(1)每次挑选价值最大的物品装入背包,得到的结果是否最优?(2)每次挑选重量最小的物品装入背包,得到的结果是否最优?(3)每次挑选单位重量价值最大的物品,价值是否最高?

 3. 可以用数学归纳法证明,我们的贪心策略应该是每次选取单位重量价值最大的的物品。

在这里插入图片描述

在这里插入图片描述

3.2 代码编写

#include<bits/stdc++.h>
using namespace std; struct item_type
{float weight; //物品重量 float value; //物品价值 float per_item_value; //单位重量物品价值 float rate; //使用百分率 
};bool cmp(item_type a, item_type b)
{return a.per_item_value > b.per_item_value;
}int main()
{int n; //n个物品float c; //背包容量为ccout << "输入物品件数和背包容量:" << endl;cin >> n >> c;item_type item[n];item[0].per_item_value=0;item[0].rate=0;item[0].value=0;item[0].weight=0;cout << "依次输入每件物品的价值和重量:" << endl;for (int i = 1; i <= n; i++){cin >> item[i].value >> item[i].weight;item[i].per_item_value = item[i].value / item[i].weight;//计算性价比item[i].rate = 0;//初始化使用率}sort(item + 1, item + n + 1, cmp);float sum = 0;int j = 1;for (j = 1; j < n; j++){if (item[j].weight <= c){item[j].rate = 1;sum = sum + item[j].value;c = c - item[j].weight; //c一直在更新 cout << "重量为:" << item[j].weight << "价值为:" << item[j].value << "的物品被放入了背包,放入比例为:" << item[j].rate << endl;}elsebreak;}//物品没装完if (j < n){item[j].rate = c / item[j].weight;c = c - item[j].rate * item[j].weight;sum = sum + item[j].rate * item[j].value;cout << "重量为:" << item[j].weight << "价值为:" << item[j].value << "的物品被放入了背包,放入比例为:" << item[j].rate << endl;cout << "背包剩余容量为:" << c;cout << "总价值:" << sum;}return 0; 
}

在这里插入图片描述

http://www.ritt.cn/news/20160.html

相关文章:

  • 百度网站推广外包电脑培训班速成班
  • 个人网站设计首页界面网络推广怎么做
  • 哪里找做鸭子的网站seo sem是指什么意思
  • 南昌网站排名推广临沂网站建设公司哪家好
  • 做网站要不要签合同怎么免费创建网站
  • 德州网站设计百度搜索引擎广告投放
  • 企业网络营销策划论文昆明seo网站建设
  • 毕业季网站如何做网页青岛seo培训
  • 昆明网站建设哪家最好网站seo系统
  • 竞价页面网站做优化网站优化工具
  • 手机网页开发者模式百度seo排名优化公司哪家强
  • 哈尔滨做平台网站平台公司吗网站点击量 哪里查询
  • 好的网站有哪些长尾关键词爱站
  • 专做旅游酒店特价网站营销助手
  • 网站建设 上海网百度的推广方式有哪些
  • 哈尔滨企业建站系统模板浙江百度代理公司
  • 自己想做个网站 费用游戏推广文案
  • 做互联网网站赚钱吗怎么去做推广
  • 如何选择合肥网站建设软文形式推广产品
  • 网站制作时友情链接翻译
  • 怎么改网站域名深圳seo推广培训
  • 网站制作用的软件有哪些天津百度网站排名优化
  • 出版社网站建设方案合肥网站制作
  • 增城网站建设网络怎么做推广
  • 石家庄专业信息门户网站定制聊城seo培训
  • 网站做管理员消息推送南宁百度seo排名公司
  • 门户网站建站注意事项电脑版百度入口
  • 做网站网什么是竞价推广
  • 做旅游网站当地人服务赚钱吗域名批量查询
  • 加强对网站建设百度网站优化排名