精华内容
下载资源
问答
  • 和最大化最小值类似,最大化平均值也可以通过二分法求得。比如下面这个经典的问题: 有n个物品的重量和价值分别是wi和vi,从中选出k个物品使得单位重量价值最大。样例输入:3 2 2 2 5 3 2 1 样例输出:0.75 分析:...

    和最大化最小值类似,最大化平均值也可以通过二分法求得。

    比如下面这个经典的问题:
    有n个物品的重量和价值分别是wi和vi,从中选出k个物品使得单位重量价值最大。

    样例输入:

    3 2
    2 2
    5 3
    2 1
    

    样例输出:

    0.75
    

    分析:

    一般先想到的是将每个物品的单位重量价值算出来,然后排个序,从大到小贪心进行选择,可惜这样是不对的,这样不能保证最后一定是最大平均值,直接用贪心对于这类要涉及多个因素比如求最大平均值的问题就显得不那么正确了。

    那么我们这样分析这个问题:
    令C(x)为可以选择使得单位重量的价值不小于x
    这样就可以用二分法来解决,不断二分x进行判断,取最大。

    我们继续分析:

     ∑vi / ∑wi 这个式子是我们需要求的单位重量的价值。 
     i∈s   i∈s
    

    那么就求是否满足:

     ∑vi / ∑wi >= x
     i∈s   i∈s
    

    转换一下得到:

    ∑(vi - x*wi) >= 0
    i∈s 
    

    判断这个式子是否成立即可。这下就可以用一个数组来保存vi - x * wi 的值,并进行排序,从大到小贪心地进行选择求和,如果求和的值大于0,那么此时 的x就是成立的。

    代码如下:

    #include<cstdio>
    #include<algorithm> 
    using namespace std;
    const int maxn = 10000+10;
    const int INF = 1000000;
    int w[maxn],v[maxn];
    double y[maxn];
    int n,k;
    
    bool C(double d)
    {
        for(int i=0; i<n; i++)
        {
            y[i] = v[i] - d * w[i];
        }
        sort(y, y+n);
    
        double sum = 0;
        for(int i=0; i<k; i++)
        {
            sum += y[n-i-1];
        }
        return sum >= 0;
    }
    void solve()
    {
        double lb = 0, ub = INF;
        for(int i=0; i<100; i++)
        {
            double mid = (lb + ub) / 2;
            if(C(mid)) lb = mid;
            else ub = mid;
        }
        printf("%.2f\n",lb);
    }
    int main()
    {
        scanf("%d%d",&n,&k);
        for(int i=0; i<n; i++)
        {
            scanf("%d%d",&w[i],&v[i]);
        }
        solve();
        return 0;
    }
    展开全文
  • 对于一组给定数据点周围的未知点求Z值采用的是比较典型的加权平均值法求值,是基于对话框形式的。
  • LeetCode 637 二叉树的层平均值

    千次阅读 2020-09-12 11:53:32
    LeetCode 637 二叉树的层平均值 题目链接 给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。 示例 1: 输入: 3 / \ 9 20 / \ 15 7 输出: [3, 14.5, 11] 典型的 BFS,每层算一个答案即可,AC代码...

    LeetCode 637 二叉树的层平均值

    题目链接

    给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。

    示例 1:

    输入:

        3
       / \
      9  20
        /  \
       15   7
    

    输出:

    [3, 14.5, 11]
    

    典型的 BFS,每层算一个答案即可,AC代码如下:

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        vector<double> averageOfLevels(TreeNode* root) {
            vector<double>ans;
            queue<TreeNode*>q;
            TreeNode* t=root;
            q.push(t);
            while(!q.empty()){
                int siz=q.size();
                double a=0,b=double(q.size());
                while(siz--){
                    t=q.front();q.pop();
                    if(t!=NULL){
                        a+=t->val;
                        if(t->left)q.push(t->left);
                        if(t->right) q.push(t->right);
                    }
                }
                ans.push_back(a/b);
            }
            return ans;
        }
    };
    
    展开全文
  • 计算二叉树每层平均值

    千次阅读 2017-08-30 23:19:34
    层次遍历计算二叉树每层平均值

    LeetCode 637. Average of Levels in Binary Tree

    Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.

    Example 1:

    Input:
        3
       / \
      9  20
        /  \
       15   7
    Output: [3, 14.5, 11]
    Explanation:
    The average value of nodes on level 0 is 3,  on level 1 is 14.5, and on level 2 is 11. Hence return [3, 14.5, 11].
    

    按照题目要求求解二叉树每层的平均值,既然按照层级求解,那么可以说是层次遍历或者说是BFS的典型问题。

    关键在于如何正确的在遍历过程中分层,思路是根据压入队列的元素个数划分。代码如下:

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        vector<double> averageOfLevels(TreeNode* root) {
            vector<double> v;
            if (root == NULL)
                return v;
            queue<TreeNode *> q;
            q.push(root);
            while (!q.empty())
            {
                int num = q.size();
                long temp = 0;
                for (int i = 0; i < num; i++)
                {
                    TreeNode *top = q.front();
                    q.pop();
                    if (top->left != NULL)
                        q.push(top->left);
                    if (top->right != NULL)
                        q.push(top->right);
                    temp += top->val;
                }
                v.push_back((double)temp / num);
            }
            return v;
        }
    };



    展开全文
  • 平均值,标准差,方差,协方差,期望,均方误差

    万次阅读 多人点赞 2018-10-12 17:04:55
    平均值,标准差,方差,协方差都属于统计数学;期望属于概率数学。 统计数学 1)平均值,标准差,方差 统计学里最基本的概念就是样本的均值、方差、标准差。首先,我们给定一个含有n个样本的集合,下面给出这些...

    1、写在前面

    平均值,标准差,方差,协方差都属于统计数学;期望属于概率数学。

    统计数学

    1)平均值,标准差,方差

    统计学里最基本的概念就是样本的均值、方差、标准差。首先,我们给定一个含有n个样本的集合,下面给出这些概念的公式描述:

    均值:

    方差:

    标准差:

    均值描述的是样本集合的中间点,它告诉我们的信息是有限的。

    方差(variance)是在概率论和统计方差衡量随机变量或一组数据时离散程度的度量。概率论中方差用来度量随机变量和其数学期望(即均值)之间的偏离程度。统计中的方差(样本方差)是各个数据分别与其平均数之差的平方的和的平均数。在许多实际问题中,研究方差即偏离程度有着重要意义。方差是衡量源数据和期望值相差的度量值。

    而标准差给我们描述的是样本集合的各个样本点到均值的距离之平均。

    以这两个集合为例,[0, 8, 12, 20]和[8, 9, 11, 12],两个集合的均值都是10,但显然两个集合的差别是很大的,计算两者的标准差,前者是8.3后者是1.8,显然后者较为集中,故其标准差小一些,标准差描述的就是这种“散布度”。之所以除以n-1而不是n,是因为这样能使我们以较小的样本集更好地逼近总体的标准差,即统计上所谓的“无偏估计”。而方差则仅仅是标准差的平方。

    方差和标准差的区别:

    方差与我们要处理的数据的量纲是不一致的,多了个平方,虽然能很好的描述数据与均值的偏离程度,但是处理结果是不符合我们的直观思维的。 而标准差的根号就抵消了这个平方,就能相对直观了描述数据与均值之间的偏离程度。

    2)协方差

    标准差和方差一般是用来描述一维数据的,但现实生活中我们常常会遇到含有多维数据的数据集,最简单的是大家上学时免不了要统计多个学科的考试成绩。面对这样的数据集,我们当然可以按照每一维独立的计算其方差,但是通常我们还想了解更多,比如,一个男孩子的猥琐程度跟他受女孩子的欢迎程度是否存在一些联系。协方差就是这样一种用来度量两个随机变量关系的统计量,我们可以仿照方差的定义:

    来度量各个维度偏离其均值的程度,协方差可以这样来定义:

    协方差的结果有什么意义呢?如果结果为正值,则说明两者是正相关的(从协方差可以引出“相关系数”的定义),也就是说一个人越猥琐越受女孩欢迎。如果结果为负值, 就说明两者是负相关,越猥琐女孩子越讨厌。如果为0,则两者之间没有关系,猥琐不猥琐和女孩子喜不喜欢之间没有关联,就是统计上说的“相互独立”。

    从协方差的定义上我们也可以看出一些显而易见的性质,如:

    3)协方差矩阵

    前面提到的猥琐和受欢迎的问题是典型的二维问题,而协方差也只能处理二维问题,那维数多了自然就需要计算多个协方差,比如n维的数据集就需要计算个协方差,那自然而然我们会想到使用矩阵来组织这些数据。给出协方差矩阵的定义:

    这个定义还是很容易理解的,我们可以举一个三维的例子,假设数据集有三个维度,则协方差矩阵为:

    可见,协方差矩阵是一个对称的矩阵,而且对角线是各个维度的方差。

    概率论

    1)期望(相当于统计数学中的均值)

    离散型

    离散型随机变量X的取值为为X对应取值的概率,可理解为数据出现的频率,则:

    连续型

    2)方差

    E(X)表示期望,X表示原始数据,其结果就为方差。当方差很小时,X的值形成的簇比较接近它们的期望值。方差的平方根被称为标准差(standard deviation)。D(X)还可以简化为:

     这里我是这么理解的:E的作用就是求平均,既然求完平均了,那么E(X)不就是一个常数了嘛,既然是常数了,拿平均自己那还是自己呀,也就是E(E(X))那不就是E(X)嘛。既然是这样那就好理解了,E(2XE(X))=2E(X)E(X),E(X)的平方那也是常数,求平均还是自己。

    另外再看一个例子:

    3)标准差

    方差的平方根被称为标准差(standard deviation)。简单来说,标准差是一组数值自平均值分散开来的程度的一种测量观念。一个较大的标准差,代表大部分的数值和其平均值之间差异较大;一个较小的标准差,代表这些数值较接近平均值。

    这里标准差和方差的区别与统计学中一样。

    均方误差

    均方误差一般被用在机器学习的预测值与真实值之间的距离。

    标准差(Standard Deviation),中文环境中又常称均方差,但不同于均方误差(mean squared error,均方误差是各数据偏离真实值的距离平方和的平均数,也即误差平方和的平均数,计算公式形式上接近方差,它的开方叫均方根误差,均方根误差才和标准差形式上接近),标准差是离均差平方和平均后的方根,用σ表示。标准差是方差的算术平方根。 
    从上面定义我们可以得到以下几点: 
    1、均方差就是标准差,标准差就是均方差 
    2、均方误差不同于均方差 
    3、均方误差是各数据偏离真实值的距离平方和的平均数 
    举个例子:我们要测量房间里的温度,很遗憾我们的温度计精度不高,所以就需要测量5次,得到一组数据[x1,x2,x3,x4,x5],假设温度的真实值是x,数据与真实值的误差e=x-xi 
    那么均方误差MSE= 
    总的来说,均方差是数据序列与均值的关系,而均方误差是数据序列与真实值之间的关系,所以我们只需要搞清楚真实值和均值之间的关系就行了。

    展开全文
  • 均方根值(RMS)、均方根误差(RMSE)、各种平均值 论文写作中经常需要比较几个算法的优略,下面列举的是一些常用的评估方法。均方根值也称作为效值,它的计算方法是先平方、再平均、然后开方。比如幅度为100V而...
  • 为什么平均值和百分位数都很棒 曾经监视或分析过应用程序的任何人都使用或曾经使用平均值。它们易于理解和计算。我们倾向于忽略那幅平均世界涂料的图画有多错误。为了强调这一点,让我给您一个我最近在报纸上看过...
  • 方法2:当前值在平均值的±3个标准差之外。 方法3:(趋势数据)moving window,该点超出邻近n个点(window)的均值±3个标准差之外,则判断为异常值。 方法4:(趋势数据)去掉该点时线性模型R方的变化,增加超过某...
  • 机器学习缺失处理方法汇总

    万次阅读 多人点赞 2017-11-26 19:44:48
    缺失处理方法综述缺失是指粗糙数据中由于缺少信息而造成的数据的聚类、分组、删失或截断。它指的是现有数据集中某个或某些属性的是不完全的。缺失的产生的原因多种多样,主要分为机械原因和人为原因。 机械...
  • 典型K平均算法中的聚类数k必须是事先给定的确定值,然而实际中很难精确确定,因而无法解决该核算法的实际问题。...实验证明,传统基于平均值方法实现数据聚类相比,用改进K值优化算法有效提高数据聚类效果。
  • 但是,你会创建定义表的数据分析表达式 (DAX) 公式,而非从数据源中查询,并将加载到新表的列中。在 Power BI Desktop 中,计算表是通过使用报表视图或数据视图中的“新建表”功能创建的。 优势:大多情况下...
  • 图像处理之二膨胀及应用

    千次阅读 2012-05-16 21:59:04
    典型的应用是在二图像 中使用这两个基本操作,是很多识别技术中重要的中间处理步骤。在灰度图像中根据阈值同 样可以完成膨胀腐蚀操作。对一幅二图像f(x,y)完成膨胀操作,对图像的卷积操作类 似,要有个...
  • 进行简单的数据处理时,我们处理的基本都是完整的数据集,但是实际问题中我们经常会遇到带有缺失的数据,处理此类数据也就显得尤为重要。 处理缺失的一般步骤 首先我们列出处理缺失的一般步骤,对整个流程有...
  • 处理后,数据范围分布将从连续属性更改为离散属性。此属性通常包含两个或多个范围。 离散化的必要性 节省计算资源,提高计算效率。 算法模型(尤其是分类模型)的计算需求。尽管决策树等许多模型可以支持连续...
  • 目录: ①边界分析法的介绍和概念 ②边界分析法的原理和思想 ③单缺陷假设和多缺陷假设 ...所谓边界,是指相对于输入等价类和输出等价类而言,稍高于其最高或稍低于最低的一些特定情...
  • 数字图像去噪典型算法及matlab实现

    千次阅读 2010-11-08 17:54:00
    数字图像去噪典型算法及matlab实现
  • 我们在前面的章节已经了解了类型和引用类型,下面我们重点讲下类型和引用类型在内存中的分配情况。 类型实例通常分配在栈(Stack)上,并且不包含任何指向实例数据的地址,因为变量包含了其实例数据。类型...
  • 信号选择器功能为从两路信号中二选一作为输出信号,信号选择器功信号输出控制方式有自动高选、自动低选、通过外部开关量/电平信号控制选择一路输入信号输出四种方式,然后将选出的信号输入信号、...
  • R语言 处理缺失数据

    万次阅读 多人点赞 2016-05-18 11:34:55
    R语言 处理缺失数据 VIM包 mice包
  • --------------------------------------------------数字图像处理领域的二十四个典型算法及vc实现、第一章一、256色转灰度图二、Walsh变换三、二化变换四、阈值变换五、傅立叶变换六、离散余弦变换数字图像处理...
  • R计算移动平均的方法

    万次阅读 2017-11-14 20:40:54
    移动平均可以使时间序列变...移动平均可以使时间序列变平滑,是典型的有序计算问题,其基本算法是:将N个连续的时间序列成员作为一个集合,计算该集合的平均值,并逐项推移该集合。下面用一个例子来说明R计算移动平均
  • 机器学习的典型例子-数据预处理

    千次阅读 2019-04-29 16:35:10
    机器学习的典型例子 根据用户的国际/年龄/薪水来推算用户是否会购买商品 自变量:国际/年龄/薪水 因变量:购买商品 取自变量: # Data Preprocessing Template # Importing the libraries import numpy as np import ...
  • 测试用例设计白皮书--边界分析方法Author: Vince 来源:http://blog.csdn.net/vincetest 一.方法简介1.定义:边界分析法就是对输入或输出的...等价划分的区别 1)边界分析不是从某等价类中随便挑一个作为代
  • 典型的x264输出如下: avis [info]: 1280x720 @ 1.77 fps (40997 frames) yuv4mpeg: 640x480@30/1fps, 0:0 x264 [info]: 352x288 (given by file name) @ 25.00 fps 取决于输入源会有不同,但大致形式一样,以上三...
  • 一个典型的锁相环(PLL)...的平均值,它同样θ有关,这样,我 们就可以利用异或门来进行相位到电压 θ 的转换,构成相位检出电路。于是经积 图3 分器积分后的平均值(直流分量)为: U U = Vdd * θ/  (1)
  • 关于奇异以及奇异分解SVD的思考

    千次阅读 多人点赞 2017-02-13 18:33:09
    前言:  SVD作为一个很基本的算法,在很多机器学习算法中都有它的身影,特别是在现在的大数据时代,由于SVD可以实现并行化,因此更是大展身手。SVD的原理不难,只要有基本的线性...回顾特征和特征向量 我们首先回
  • R语言计算移动平均的方法

    千次阅读 2014-10-13 11:53:50
    移动平均可以使时间序列变平滑,是典型的有序计算问题,其基本算法是:将N个连续的时间序列成员作为一个集合,计算该集合的平均值,并逐项推移该集合。下面用一个例子来说明R计算移动平均的方法。案例描述:数据框...
  • 典型例子是求股票的n天内的平均值。 移动平均的关键是如何求这个平均值,可以使用Queue来实现。 public class MovingAverageDriver { public static void main(String[] args){ SparkConf conf = new SparkC

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 90,708
精华内容 36,283
关键字:

典型值与平均值