展开

关键词

-LeetCode 55、45(,跳跃

:LeetCode #55 #45 1 编程 【LeetCode #55】跳跃游戏 给定一个非负整数数组,你最初位于数组的第一个位置。 原理: 遍历整个nums数组,每次计从i位置的最大可能到达的距离,然后依次更新这个最大值,如果最大值大于nums的大小nums.size(),那么就返回true, 否则返回false. 这就是正常人取求解这个的思路,很容易想到的! C++代码: class Solution { public: bool canJump(vector<int>& nums) { int maxReach = ; 说明: 假设你总是可以到达数组的最后一个位置 原理: 由于目中规定总能到达数组的最后一个位置,因此我们在遍历数组时每次都要去找最大的跳跃位置,只有到达了这个最远的边界end,我们才让step进行自加

66760

之背包

(又称)是指,在对求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。 不是对所有都能得到整体最优解,关键是策略的选择,选择的策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关。 完全背包:给定n个物品和一个容量为C的背包,物品i的重量是Wi,其价值为Vi,背包是如何选择入背包的物品,使得装入背包的物品的总价值最大,与0-1背包的区别是,在完全背包中,可以将物品的一部分装入背包 设计的思路很简单,计物品的单位价值,然后尽可能多的将单位重量价值高的物品放入背包中。 python实现代码如下: 1 # coding=gbk 2 # 完全背包 3 import time 4 __author__ = 'ice' 5 6 7 class

79360
  • 广告
    关闭

    腾讯云精选爆品盛惠抢购

    腾讯云精选爆款云服务器限时体验20元起,云数据库19.9元/年起,还有更多热门云产品满足您的上云需求

  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    活动安排--

    活动安排就是要在所给的活动集合中选出最大的相容活动子集合,是可以用有效求解的很好例子。该要求高效地安排一系列争用某一公共资源的活动。 提供了一个简单、漂亮的方使得尽可能多的活动能兼容地使用公共资源。    也就是说,该选择的意义是使剩余的可安排时间段极大化,以便安排尽可能多的相容活动。   此的效率极高。 并不总能求得的整体最优解。但对于活动安排却总能求得的整体最优解,即它最终所确定的相容活动集合A的规模最大。这个结论可以用数学归纳证明。 A[i] = true; j=i; } else A[i] = false; } } 应用实例: 描述

    1.8K60

    (集合覆盖)

    这个就是经典的用求解的是指在每一步选择中都采取最优的策略,从而希望能够导致结果是最优的一种所得到的结果并不一定是最优的解,但都是相对接近最优解的结果。 二、案例: 要解决上面的,该怎么做呢?常规的做如下: 列出k1、k2、k3、k4、k5的所有可能组合,总共就有2^5 = 32中组合。怎么来的?就是5个数不考虑顺序进行排列组合嘛。 在这32中组合中挑选一种可以覆盖到8个地区,并且广播台最少的组合,那就是本的解了。 这样做显然很麻烦,要是有100个广播台,那不是完犊子了。但是可以使用,提高效率。 步骤如下: 遍历所有的广播台,找到一个包含了最多当前还未覆盖地区的广播台; 将这个广播台存起来,想办把该广播台覆盖的地区中下次选择时,用别的广播台代替; 重复上面的步骤直到覆盖了所有的地区。 三、代码实现: 将上面的用代码实现出来。

    43720

    C++】集锦(14):

    文章目录 跳跃游戏 I 思路分析 代码实现 跳跃游戏 II 思路 可以理解为一种特殊的动态规划为,拥有一些更加特殊的性质,可以进一步降低动态规划的时间复杂度。 但是呢,我们今天讲的是,它可以想象成从上往下一条路走下去。让我们看看: ---- 思路 是什么?会选择当下最有潜力的一步。 动归的话会递归去这两步到最终结果的最优步数,但是不这样。 是每次尽可能多跳吗? NoNoNo,选择当下最有潜力的:在坐标1的位置,你有三个选择;在坐标2的位置,你只有一个选择,所以会让你选择跳到坐标1。 这就是的局部最优(不要奇思妙想啥反例,要用,就要承担它的失误率)。

    7710

    之区间调度

    什么是呢?可以认为是动态规划的一个特例,相比动态规划,使用需要满足更多的条件(选择性质),但是效率比动态规划要高。 比如说一个使用暴力解需要指数级时间,如果能使用动态规划消除重叠子,就可以降到多项式级别的时间,如果满足选择性质,那么可以进一步降低时间复杂度,达到线性级别的。 然而,大部分都明显不具有选择性质。比如打斗地主,对手出对儿三,按照策略,你应该出尽可能小的牌刚好压制住对方,但现实情况我们甚至可能会出王炸。 这种情况就不能用,而得使用动态规划解决,参见前文 动态规划解决博弈。 一、概述 归正传,本文解决一个很经典的 Interval Scheduling(区间调度)。 二、 这个有许多看起来不错的解决思路,实际上都不能得到正确答案。比如说: 也许我们可以每次选择可选区间中开始最早的那个?

    58010

    (二)——一般背包

    注:背包分为两种,若每个物体不可分割,则称为0/1背包,这种求的最优解,只能求的近似解。而若每个物体可以切分,则称为一般背包,可以使用求的最优解。 目标函数 使用解决最优化的第一步,就是要从目中抽象出目标函数,这是一个数学建模的过程。 本中,目标函数就是当前背包收益的最大值: ? 最优量度准则2:价值高的物体优先 这种选也无达到整体最优解,理由同上。 最优量度准则3:性价比高的物体优先 首先计所有物体的性价比(重量和收益的比值),每次优先将性价比高的物体放入背包。 lastBody = bodys.get(i); results.add(new Body(lastBody.id,rest,(lastBody.p*rest/lastBody.w)); } 总结 要用解决一个最优化 最优量度标准的选择往往是先根据经验,然后再通过数学归纳的方式证明它能导致整体最优解。 若无选出一个最优量度标准,则可以使用动态规划解决最优化

    1.1K70

    笔记(0002) - 【】活动安排

    笔记(0002) - 【】活动安排 原理 在对求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。 特性 采用自顶向下,以迭代的方做出相继的选择,每做一次选择就将所求简化为一个规模更小的子,通过每一步选择,可得到的一个最优解,虽然每一步上都要保证能获得局部最优解,但由此产生的全局解有时不一定是最优的 能够用求解的一般具有两个重要特性:选择性质和最优子结构性质。 1、选择性质 所谓选择性质是指所求的整体最优解可以通过一系列局部最优的选择,即选择来达到。 这是可行的第一个基本要素。则通常以自顶向下的方式进行,以迭代的方式作出相继的选择,每作一次选择就将所求简化为规模更小的子。 ACM––活动安排

    48120

    C经典

    输出九九乘口决表。 古典:有一对兔子,从出生第三个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,每个月的兔子总数是多少? 分析:前两个数之和为第三个数的值,即有名的斐波那契数列。 if(n<m){ temp = n; n = m; m = temp; }; p=n*m; // 欧几里德 // 100 模 60 余 40 // 60 分析:利用while句,条件为输入的字符不为'\n'。 猴子吃桃:猴子第一天吃下若干个桃子,当即吃下一半,还不过瘾,又多吃了一个,第二天又将剩下的桃子吃了一半,又多吃了一个,以后每天都吃前一天剩下的一半零一个,到第10天想早上再吃时,只剩下一个桃子了。

    16330

    -活动选择(Python实现)

    # 活动安排就是要在所给的活动集合中选出最大的相容活动子集合, # 是可以用有效求解的很好例子。 # 该要求高效地安排一系列争用某一公共资源的活动。 # 提供了一个简单、漂亮的方使得尽可能多的活动能兼容地使用公共资源。 import ioTool #编程任务:在所给的活动集合中选出最大的相容活动子集合。

    50320

    -分数背包(Python实现)

    81010

    0-1背包

    背包 有一个背包,背包容量是M=150。有7个物品,物品可以分割成任意大小。 要求尽可能让装入背包中的物品总价值最大,但不能超过总容量。 物品 A B C D E F G 重量 35 30 60 50 40 10 25 价值 10 40 30 50 35 40 30 描述: 1.改变数组w和v的排列顺序,使其按单位重量价值v[ i]/w[i]降序排列; 2.将数组x[n]初始化为0; //初始化向量 i=1; 4.循环直到(w[i]>C); 4.1 x[i]=1; 4.2 C=C-w[i]; 4.3 i++; x[i]=C/w[i]; **/ public class Package2 { public static void main(String[] args) { { x[i] = 1; c = c - w1[i]; maxValue += v1

    23830

    --零钱找零

    描述:现在有2元、1元、0.5元、0.2元、0.1元、0.05元的纸币,如何才能使得找零的的张数最小 基本思路;将纸币从大到小排序,尽可能地先找大额的; coins = [2,1,0.5,0.2,0.1,0.05

    21520

    --活动安排

    描述:现有一批活动,有开始时间和结束时间,如何合理的安排使得尽可能多的活动得以开展; 活动 讲座 会议 演出 电影 辩论赛 考试 开始时间 1 3 0 5 3 7 结束时间 3 4 4 7 6 8 解思路:如何才能保证安排更多的活动呢? 最后就是核。由于结束时间已经是排好序的了,我们只要关注于开始时间,如果和前面的结束时间没有冲突,就可以进行这个活动。 总结:就是要让每一步都最优。

    13320

    Day9 :变态跳台阶

    具体要求: 时间限制: C/C++ 1秒,其他2秒 空间限制: C/C++32M,其他64M 具体思路: 背景知识介绍   相信大家都听说过,但是大家或许没有系统的了解过。 比如在旅行推销员中,如果旅行员每次都选择最近的城市,那这就是一种。   在有最优子结构的中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。 一旦一个可以通过来解决,那么一般是解决这个的最好办。 由于的高效性以及其所求得的答案比较接近最优结果,也可以用作辅助或者直接解决一些要求结果不特别精确的。    的基本思路:建立数学模型来描述、把求解的分成若干个子、对每个子求解,得到子的局部最优解、把子的解局部最优解合成原来的一个解。

    23851

    使用解决集合覆盖

    在《图解》里面有一个蛮有意思的小案例,背景是一个广播节目,要让全美的50个周的听众都能够听到,但是每个电台可能覆盖多个州,每在一个电台播出就需要一笔费用,所以就是从成本的角度来看,怎么尽可能在所有的州都播出 ,这是一个典型的集合覆盖的,而且在我们的生活中是比较典型。 比如我们先缩小范围,指定5个州,那么50个州也是同样的。 如何使用呢,就是选择覆盖尽可能多的州的电台,然后逐步缩小范围。那么覆盖面广的州所对应的电台就优先被选中,依次类推。 当然得到的不是精确的结果,即可能不是最优解,是一种近似,能够基本得到的最优解,而且效率很高。

    44420

    Day67:剪绳子

    示例1 输入 8 输出 18 具体要求: 时间限制: C/C++ 1秒,其他2秒 空间限制: C/C++32M,其他64M 具体实现: 背景知识介绍:   在做之前 一旦一个可以通过来解决,那么一般是解决这个的最好办。由于的高效性以及其所求得的答案比较接近最优结果,也可以用作辅助或者直接解决一些要求结果不特别精确的。 4、把子的解局部最优解合成原来解的一个解。   一般而,对于大部分的通常都不能找出最佳解(不过也有例外),因为他们一般没有测试所有可能的解。 具体我们用java和python两门将其实现。 本文给出了两种解思路:即动态规划与。并且分别用java和python两门编程将其实现。这里需要我们注意的是:尽管效率更高了。不过并不是所有都可以采用婪策略得到最优解。

    26131

    相关产品

    • 云服务器

      云服务器

      云端获取和启用云服务器,并实时扩展或缩减云计算资源。云服务器 支持按实际使用的资源计费,可以为您节约计算成本。 腾讯云服务器(CVM)为您提供安全可靠的弹性云计算服务。只需几分钟,您就可以在云端获取和启用云服务器,并实时扩展或缩减云计算资源。云服务器 支持按实际使用的资源计费,可以为您节约计算成本。

    相关资讯

    热门标签

    扫码关注云+社区

    领取腾讯云代金券