唯品会一家专门做特卖的网站,怀化住建部网站,用手机怎么做免费网站,wordpress的模板文件下载文章目录 一、贪心算法概述二、活动安排问题2.1 问题概述2.2 代码编写 三、背包问题3.1 问题描述3.2 代码编写 一、贪心算法概述 1. 贪心算法的定义#xff1a;贪心算法是指在对问题求解时#xff0c;总是做出在当前看来是最好的选择。也就是说#xff0c;不从整体最优上加以… 文章目录 一、贪心算法概述二、活动安排问题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. 不需要我们排序的代码
#includebits/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;cinn;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){cins[i]f[i];}activity_select(n,s,f,selected);cout有如下活动被选择endl;for (int i 1; i n; i){if (selected[i] 1){couti ; }} return 0;
}2. 需要我们排序的代码
#includebits/stdc.h
#includeiostream
using namespace std; struct activity //活动结构体
{int start;int end;
};bool cmp(activity a,activity b) //cmp参数为sort函数的排序准则设置为按照活动的结束时间由小到大排序
{ return a.endb.end;
} void activity_select(int n,int selected[],activity act[])
{ int i1;selected[1]1; for(int j2;jn;j) //从结束时间倒数第二小的活动开始遍历 { if(act[j].startact[i].end) { ij; selected[j]1; } else{selected[j]0;}}
}int main()
{cout请输入活动的个数;int n;cinn;int selected[n]; //若活动i被选择则selected[i]置1否则置0activity act[n];cout请输入活动的开始和结束时间(按照结束时间升序输入)endl; for(int i1;in;i){cinact[i].startact[i].end;}act[0].start-1;act[0].end-1;sort(act1,actn1,cmp); //act1表示第2个元素(i1,第1个活动) activity_select(n,selected,act); cout有如下活动被选择endl;for (int i1; in; i){if (selected[i]1){couti ; }} 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 代码编写
#includebits/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_value0;item[0].rate0;item[0].value0;item[0].weight0;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;
}
