1 #include "iostream" 2usingnamespace std;3 4float MAX(float m1,float m2){5if(m1>=m2)6return m1;7else 8return m2;9}
1011float bag_Zero_One(int n,float v,float p[],float w[]){
12if(n==0||v==0)
13return0;
14else{
15float m2;
1617 m2=bag_Zero_One(n-1,v,p,w);
18if(v>=w[n]){
19float m1;
20 m1=bag_Zero_One(n-1,v-w[n],p,w)+p[n];
21 m2=MAX(m1,m2);
22 }
23return m2;
2...
红黑树(red-black tree)是一种“平衡”查找树,它能保证最坏情况下,基本的动态集操作时间为O(lgn).性质:1)每个节点要么是红的,要么是黑的2)根节点和叶子节点(NIL)是黑色的3)若一个节点是红色的,则他的两个孩子节点是黑色的4)对于每一个节点x,从该节点到其子酸节点的所有路径上包含相同数目的黑节点(#black nodes = black-height(x))引理: 一棵有n个内节点的红黑树的高度至多为 2 lg(n+1)红黑树上插入删除的完整代码...
1. 概念:Binary-search tree(BST)是一颗二叉树,每个树上的节点都有<=1个父亲节点,ROOT节点没有父亲节点。同时每个树上的节点都有[0,2]个孩子节点(left child AND right child)。每个节点都包含有各自的KEY值以及相应的satellite data。其中KEY是几种BST基本操作的主要操作对象。 2. BST的特别性质:BST任何一颗子树上的三个节点left, parent, right. 满足条件left.key<parent.key<=right.key一颗典型的BST如下图所示: 观察之...
15.1钢条切割#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<ctime>
#include<string>
using namespace std;
int p[1000]{ 0,1,5,8,9,10,17,17,20,24,30 };//钢条价格。长度i的价格为p[i]
int ordinary(int *p, int n)//递归法
{if (n == 0)return 0;else{int q = -1;for (int i = 1; i <= n; ++i){q = max(p[i] + ordinary(p, n - i), q);}return q;}
}
int top_down_memory(int *p, int n)/...
package org.loda.graph;import org.loda.structure.Stack;
import org.loda.util.In;/***
* @ClassName: Topological
* @Description: 拓扑排序是所有节点dfs的逆后序,也就是每个节点任务完成的时间的逆序排序
* @author minjun
* @date 2015年5月24日 下午7:17:53
**/
public class Topological {/*** 由于拓扑排序是df获取所有节点的逆后序排序* 这里利用Stack后序存储元素,那么获取出来就是反向(逆)后序排列的拓顺序*/...
前面我们学习二叉搜索树的时候发现在一些情况下其高度不是很均匀,甚至有时候会退化成一条长链,所以我们引用一些”平衡”的二叉搜索树。红黑树就是一种”平衡”的二叉搜索树,它通过在每个结点附加颜色位和路径上的一些约束条件可以保证在最坏的情况下基本动态集合操作的时间复杂度为O(nlgn).下面会总结红黑树的性质,然后分析红黑树的插入操作,并给出一份完整代码。先给出红黑树的结点定义:#define RED 1#define BLACK 0///红黑...
课程地址http://v.163.com/special/opencourse/algorithms.html今天课程地址:http://open.163.com/movie/2010/12/G/F/M6UTT5U0I_M6V2T1JGF.html讨论performanceAnalysis of Algorithms: the study of computer program performance ans resource usage.Thinking: What is more important than performance?Functionality, modularity, user-friendliness, security...Then why study algs and perf?performance is like the "money...
斐波那契堆是具有最小堆序的有根树的集合,也就是集合中的每棵树都具有父结点的关键字小于或等于子结点的关键字。 对于每一个结点x,主要有以下属性:名称说明记作关键字结点存储的值x.key父结点结点的父亲x.p左兄弟结点的左兄弟x.left右兄弟结点的右兄弟x.right孩子结点的一个儿子结点x.child度结点的儿子数量,不包括孙子及下层x.degree标记结点是否有儿子被删除x.mark堆H本身属性:名称说明记作最小结点最小的根结点H.min结点数...
动态规划算法概述 动态规划(dynamic programming)1是一种与分治方法很像的方法,都是通过组合子问题的解来求解原问题。不同之处在于,动态规划用于子问题重叠的情况,比如我们学过的斐波那契数列。在斐波那契数列的求解问题中,我们经常要对一个公共子问题进行多次求解,而动态规划算法,则对每个子问题只求解一次,将其解保存在一个表格中,从而避免了大量的冗余计算量。 动态规划算法常用于寻找最优解问题(optimization pro...
散列表是主要支持动态集合的插入、搜索和删除等操作,其查找元素的时间在最坏情况下是O(n),但是在是实际情况中,散列表查找的期望是时间是O(1),散列表是普通数组的推广,因为可以通过元素的关键字对数组进行直接定位,所以能够在O(1)时间内访问数组的任意元素。1、直接寻址表当关键字的全域较小,即所有可能的关键字的量比较小时,可以建立一个数组,为所有可能的关键字都预留一个空间,这样就可以很快的根据关键字直接找到对应元...
什么是基础呢? 就是要把我们大学所学的离散数学,算法与数据结构,操作系统,计算机体系结构,编译原理等课程学好。对计算机的体系,CPU本身,操作系统内核,系统平台,面向对象编程,程序的性能等要有深层次的掌握。要编写出优秀的代码同样要扎实的基础,如果数据结构和算法学的不好,怎么对程序的性能进行优化,怎样从类库中选择合适的数据结构。如果不了解操作系统,怎样能了解这些开发工具的原理,它们都是基于操作系统的。不...
1、算法思想
问题描述:从数组array中找出第i小的元素(要求array中没有重复元素的情况),这是个经典的“线性时间选择(Selection in expected linear time)”问题。
思路:算法导论215页9.2 Selection in expect linear time
2、java实现
思路:算法导论216页伪代码/*期望为线性时间的选择算法,输入要求,array中没有重复的元素*/public static int randomizedSelect(int[] array,int start,int end,int i) {if (start==end) {...
一、动态规划的概念 动态规划(Dynamic Programming)是通过组合子问题的解而解决整个问题的。分治算法是指将问题划分成一些独立的子问题,递归地求解各子问题,然后合并子问题的解而得到原始问题的解,与此不同,动态规划适用于子问题不是独立的情况,也就是各个子问题包含公共的子问题。在这种情况下,采用分治法会做许多不必要的工作,即重复地求解公共地子问题。动态规划算法对每个子问题只求解一次,将其结果保存在一张...
目录 1、分治求x的n次方思路 2、c++代码实现内容 1、分治求x的n次方思路T(n)=Θ(lgn) 为了计算乘方数a^n,传统的做法(所谓的Naive algorithm)就是循环相乘n次,算法效率为Θ(n)。但是如果采用分治法的思想,算法效率可以提高到Θ(lgn),如...
原创博客,转载请注明:http://www.cnblogs.com/wuwenyan/p/4982713.html 当算法的输入n非常大的时候,对于算法复杂度的分析就显得尤为重要,虽然有时我们能通过一定的方法得到较为精确的运行时间,但是很多时候,或者说绝大多数时候,我们并不值得去花精力求得多余的精度,因为精确运行时间中的倍增常量和低阶项已经被输入规模本身的影响所支配。我们需要关心的是输入规模无限增加,在极限中,运行时间是如何随着输入规模增大...