精华内容
下载资源
问答
  • 贪心选择性质的证明

    千次阅读 2019-04-12 15:55:30
    1、贪心选择性质:在求解一个最优化的过程中,使用贪心的方式选择了一组内容之后,不会影响下面的子问题的求解。 2、 如果无法使用贪心性质,只需要举出一个反例就可以了 3、比如0-1背包问题 但是这个...

    1、贪心选择性质:在求解一个最优化的过程中,使用贪心的方式选择了一组内容之后,不会影响下面的子问题的求解。

     

    2、

    如果无法使用贪心性质,只需要举出一个反例就可以了

     

     

    3、比如0-1背包问题

    但是这个问题将1号物品和2号物品放进背包,最终得到的价值是10+12=22,这样一个反例就告诉我们贪心算法不成立

    4、

    直觉解法就是把比这个数小的最大的完全平方数加进这个数中,比如对于12来说,最大的完全平方数是9,剩下的事情是凑3,那么比3小的最大的完全平方数就是1,最终使用贪心的算法求解出12=9+1+1+1,一共使用了4个完全平方数,可是,12可以使用3个4来表示,那么,这个反例就告诉我们,贪心算法是不成立的。对于这两个问题来说,可以说是不包含贪心选择性质的。

     

    5、

    如果在算法领域,遇到了需要使用数学证明的问题,通常首先想到的是使用两种方式,这两种方式分别是数学归纳法和反证法。数学归纳法相当于是递推的过程,就像动态规划的过程,将基本的问题解决之后,假设规模为n的问题可以解决,就能推导出规模为n+1这样的问题。对于数学归纳法所适用的领域,通常都是有一个变量n在逐渐增加的过程。对于现在这个问题,显然不是这样的。另外一种在数学领域经常使用的就是反证法,所谓反证法就是假设它不正确,然后看可不可能推导出矛盾。

     

    6、

     

     

     

    7、

    8、

     

    展开全文
  • 背包问题贪心选择性质证明

    千次阅读 2018-06-12 11:19:20
    对于背包问题可以用贪心算法求解,作为01背包的上界函数下面证明背包问题满足贪心选择性质:设有一按照单位价值排序好的最优解T=(tk,....tn)第一个装入的物品是tk若k=1则存在贪心性质出发的最优解若k不等于1:如果...

    对于背包问题可以用贪心算法求解,作为01背包的上界函数


    下面证明背包问题满足贪心选择性质:

    设有一按照单位价值排序好的最优解T=(tk,....tn)

    第一个装入的物品是tk


    若k=1则存在贪心性质出发的最优解

    若k不等于1:

    如果物品k比物品1重,将k物品中物品1重量的部分卸下,换成物品1,构造新的解T',满足容量约束,且背包价值优于T

    如果物品1比k重,则将k卸下,装上1物品的一部分(与物品k同样重量),满足容量约束,且背包价值优于T


    因此总存在以贪心性质开始的最优解,由数学归纳法可以得到满足贪心性质的最优解。

    展开全文
  • 1. 试证明哈夫曼问题具有贪心选择性质: 二叉树T表示字符集C的一个最优前缀码,证明可以对T作适当修改后得到一棵新的二叉树T”,在T”中x和y是最深叶子且为兄弟,同时T”表示的前缀码也是C的最优前缀码。设b和c是...

    1. 试证明哈夫曼问题具有贪心选择性质:

     二叉树T表示字符集C的一个最优前缀码,证明可以对T作适当修改后得到一棵新的二叉树T”,在T”中x和y是最深叶子且为兄弟,同时T”表示的前缀码也是C的最优前缀码。设b和c是二叉树T的最深叶子,且为兄弟。设f(b)<=f(c),f(x)<=f(y)。由于x和y是C中具有最小频率的两个字符,有f(x)<=f(b),f(y)<=f(c)。首先,在树T中交换叶子b和x的位置得到T',然后再树T'中交换叶子c和y的位置,得到树T''。如图所示:

        由此可知,树T和T'的前缀码的平均码长之差为:

         因此,T''表示的前缀码也是最优前缀码,且x,y具有相同的码长,同时,仅最优一位编码不同。

    2. 试证明哈夫曼问题具有最优子结构性质:

     二叉树T表示字符集C的一个最优前缀码,xy是树T中的两个叶子且为兄弟,z是它们的父亲。若将z当作是具有频率f(z)=f(x)+f(y)的字符,则树T’=T-{x,y}表示字符集C’=C-{x, y} { z}的一个最优前缀码。因此,有:

         如果T’不是C’的最优前缀码,假定T”C’的最优前缀码,那么有

    ,显然T”’是比T更优的前缀码,跟前提矛盾!故T'所表示的C'的前缀码是最优的。

    展开全文
  • 贪心选择性质(数学归纳法) 先设一个最优解A⊆EA\subseteq EA⊆E(EEE为所给定的总元素集合,且AAA和EEE均按照某种有利于算法贪心进行的顺序进行排序),并且设kkk为最优解的第一个元素(即k=min1≤i≤n{i∣xi=1}k=...

    最优子结构性质(反证法

    • 计算某问题的最优解包含的计算该问题的子问题也是最优解。事实上,如果找到子问题的更优解,则可以替换当前子问题的解,得到一个比最优解更优的解,这是一个矛盾。

    贪心选择性质(数学归纳法

    • 先设一个最优解AEA\subseteq E(EE为所给定的总元素集合,且AAEE按照某种有利于算法贪心进行的顺序进行排序),并且设kk为最优解的第一个元素(即k=min1in{ixi=1}k=min_{1\leq{i}\leq{n}}\{i|x_i=1\})。
    • 1)当k=1k=1时,AA就是一个以贪心选择开始的最优解;
    • 2)当k1k\geq 1时,设B=A{k}{1}B=A-\{k\}\cup\{1\},由于AA的价值与BB的价值相等(即AA能做到的BB也可以做到),且AA是最优的,故BB也是最优的,因此BB是以贪心选择元素1开始的最优解。
    展开全文
  • 在前面学习最短路径和最小生成树的时候,我们发现Dijkstra算法,Prim算法,Kruskal算法都是属于 贪心算法的应用。...贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择选择贪心策略必须...
  • 性质)的证明,是我们的作业,奈何本人数学渣,依旧不能根据课本依葫芦画瓢,来此求救。 首先铺垫: <p style="text-align:center"><img alt="" height="352" src=...
  • 部分背包问题贪心选择性质的证明

    万次阅读 2014-11-01 13:13:01
    最近算法课讲到贪心算法,感觉书本上对bufentanxin
  • 写公式比较麻烦,所以干脆就在纸上写好之后,把照片贴上来。
  • 本课程是从少年编程网转载的课程,目标是向中学生详细介绍计算机比赛涉及的编程语言,数据结构和算法。...之前的课程中,我们学习了运用贪心算法...贪心算法逐步构建问题的解决方案,总是选择能直接带来当前最大利益...
  • 按照自己的理解写的
  • 算法分析: 采用最长处理时间作业优先的贪心选择策略,可以设计出解多机调度问题较好的近似算法。分n(作业数小于机器数),n>m(作业数大于机器数)求解。假定有7个独立作业,所需处理时间分别为{2,14,4,16,6,5,...
  • #include #include #include #include #include #include #include #define Bug cout ; using namespace std; const int N = 1005; struct node { double s, f; }t[N];...bool cmp(const node a
  • 具有下面两个条件的问题就可以使用贪婪法进行求解,而且满足这两个条件是可以求出最优解的: 具备贪心选择性质 - 全局最优解可以由局部最优解推导出来,这个条件通常不那么容易满足。 具备最优子结构 - 整个问题的...
  • 从全连通和没有环路这两个性质出发,我们又可以得到一个很重要的结论,对于一棵拥有n个节点的树而言,它的边数是固定的,一定是n-1条边。如果超过n-1条边,那么当中一定存在环路,如果小于n-1条边,那么一定存在不...
  • 从全连通和没有环路这两个性质出发,我们又可以得到一个很重要的结论,对于一棵拥有n个节点的树而言,它的边数是固定的,一定是n-1条边。如果超过n-1条边,那么当中一定存在环路,如果小于n-1条边,那么一定存在不...
  • 关于贪心选择正确性的证明

    千次阅读 2018-01-11 22:42:14
    贪心选择性质:一个全局最优解可以通过局部最优得到。即存在一个最优解是以贪心选择开始的。 证明思路: 先考察一个全局最优解,然后对该解加以修改(一般是采用“剪枝”技巧),使其采用贪心选择,这个选择将原...
  • 分数背包贪心选择性的证明

    千次阅读 2018-06-10 17:24:16
    贪心选择性质:问题的整体最优解可以由一系列子问题的最优选择,既贪心选择得到。问题描述:假设有n个物体C1,n分别标记为:1, 2, …, n。其价值分别为:V1, V2,…, Vn,重量分别为:W1, W2, …, Wn。背包的容量为W...
  • 问题可以描述为:该问题可以用贪心算法求解,要使用贪心算法解决问题,我们必须先证明:(1)该问题具备贪心选择性质;(2)该问题具备最优子结构性质.1> 首先先证明贪心选择性质:设集装箱已依其重量从大到小...
  • 摘要 当一个问题具有最优子结构性质时,可用动态规划...关键词 贪心算法,贪心选择性质,最优子结构性质,哈夫曼算法,三元码 1问题简述哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%~...
  • 贪心算法(又称贪婪算法Greedy):在对问题求解时,...可用贪心算法求解的问题一般有两个重要性质:1、贪心选择性质在当前状态下做出最好选择,即局部最优选择,然后再去解决做出这个选择后产生的响应的子问题,通常...
  • 贪心

    2019-04-23 16:20:03
    /* 1)贪心的基本思想:求解最优化问题的算法通常要 经过一系列步骤,每个步骤都面临多种选择, 它在每个决策点作出在当时看来最佳的选择, ... 2)两个要素:贪心选择性质+最优子结构 1.贪心选择性质:...
  • 贪心

    万次阅读 2016-05-07 19:44:50
    贪心选择性质: 1、 活动安排 : 问题描述 :设有n个活动集合E = {1 ,2,…,n} ,其中每个活动i都要求使用同一资源, 而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始
  • 贪心算法与活动选择问题 C++实现

    千次阅读 2016-11-12 15:00:15
    贪心算法与活动选择问题贪心算法原理在之前的文章里,作者讲过动态规划,然而贪心算法和...贪心算法需要两个关键的要素—-贪心选择性质与最优子结构。贪心选择性质我们可以通过做出局部最优选择来构造全局最优解。在
  • 贪心算法

    2019-09-28 04:54:24
    贪心选择的一般特征:贪心选择性质和最优子结构性质。 贪心选择性质: 所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。这是贪心算法可行的第一个基本要素,也是贪心...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 657
精华内容 262
关键字:

贪心选择性质