有哪些信誉好的足球投注网站- 1、有哪些信誉好的足球投注网站（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。。
- 2、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击 这里二次下载。
- 3、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。
查看更多
教学课件课件PPT医学培训课件教育资源教材讲义
第2部分 算法设计策略;6.1 一般方法
6.2 背包问题
6.3 带时限的作业排序
6.4 最佳合并模式
6.5 最小代价生成树
6.6 单源最短路径
6.7 磁带最优存储
6.8 贪心法的基本要素 ;最优化问题（optimization problems）是指这样一类问题，问题给定某些约束条件（constraint），满足这些约束条件的问题解称为可行解（feasible solution）。通常满足约束条件的解不是惟一的。为了衡量可行解的好坏，问题还给出了某个数值函数，称为目标函数（objective function），使目标函数取最大（或最小）值的可行解称为最优解（optimal solution）。;贪心法是通过分步决策（stepwise decision）的方法来求解问题的。
贪心法每一步上用作决策依据的选择准则被称为最优量度标准（optimization criterion）。
在根据最优量度标准选择分量的过程中，还需要使用一个可行解判定函数。
贪心策略并不是从整体上加以考虑的，它所做出的选择只是当前看似最佳选择，必须进一步证明该算法最终导致问题的一个整体最优解。;贪心技术(Greedy Technique);【程序6－1】贪心法
SolutionType Greedy(SType a[],int n)
{
SolutionType solution=?;
for(int i=0;in;i++){
SType x=Select(a);
if (Feasiable(solution,x))
solution=Union(solution,x);
}
return solution;
};*;*;贪心策略最优解的证明; 问题
对容量为M的背包进行最佳装载的问题。; 背包问题的最优解必须使下列目标函数取最大值：;例6－1
设有载重能力M=20的背包，3件物品的重量为:（w0,w1,w2）=(18,15,10)，物品装入背包的收益为：（p0,p1,p2）=(25,24,15)。;背包问题(Knapsack Problem); ; 【程序6－2】背包问题的贪心算法
templateclass T
class Knapsack
{
public:
Knapsack(int mSize,float cap,float *wei,T *prof);
void GreedyKnapsack(float* x);
……
private:
float m,*w;
T *p;
int n;
};;templateclass T
void KnapsackT::GreedyKnapsack(float* x)
{ //前置条件：w[i]已按p[i]/w[i]的非增次序排列
float u=m;
for (int i=0;in;i++) x[i]=0;
for (i=0;in;i++) {
if (w[i]u) break;
x[i]=1.0;
u=u-w[i];
}
if (i=n) x[i]=u/w[i];
}
?;6.2.3? 算法正确性;证明：
设X=(x0, x1, …, xn-1)， 0≤xj ≤ 1 ,0≤i＜n是贪心背包算法所生成的贪心解。
① 如果所有的xi都等于1,则显然X就是问题的最优解。否则，
设j是使xi≠1的最小下标。由算法的执行过程可知，
解的形式为：
X=(1, …, 1,xj,0, …, 0)
即xi=1 0≤i＜j, 0≤xj ＜1,xi=0 j＜i≤n-1; 假设Y是问题的最优解：Y=(y0, y1, …, yn-1) 且有：
● 若X ＝ Y，则X就是最优解。否则，
● X和Y
文档评论（0）