背包问题(贪心)

背包问题(贪心)
贪心算法关键:找出最优量度 利用一道ACM的题目,熟练贪心: 描述 现在有很多物品(它们是可以分割的),我们知道它们每个物品的单位重量的价值v和重量w(1<=v,w<=10);如果给你一个背包它能容纳的重量为m(10<=m<=20),你所要做的就是把物品装到背包里,使背包里的物品的价值总和最大。 输入 第一行输入一个正整数n(1<=n<=5),表示有n组测试数据; 随后有n测试数据,每组测试数据的...

二分检索(分治)

二分检索(分治)
分治二分检索 基本思路:1 ,2 ,3 ,4 ,5,6 ,7,8,9在这9个元素中(有序数组),请检索元素5,是否在这9个元素中,如果利用普通的循环的话如果这堆元素有很大,比如说10000000个元素,计算机肯定会超时!利用分治的思想可以很好的解决这个问题! 示例: 6个元素数组(23 34 46 768 343 343),检索给出的4个数(2 4 23 343)是否在数组中,是的话输出YES,否则NO [cpp] #include <iostream> #include <algorit...

白话经典算法系列之三 希尔排序的实现

白话经典算法系列之三 希尔排序的实现
资料来源于互联网,版权为:MoreWindows! 希尔排序(Shell Sort)是插入排序的一种。是针对直接插入排序算法的改进。该方法又称缩小增量排序,因DL.Shell于1959年提出而得名。 基本思想是:先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序。因为直...

白话经典算法系列之二 直接插入排序的三种实现

白话经典算法系列之二 直接插入排序的三种实现
直接插入排序(Insertion Sort)的基本思想是:每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子序列中的适当位置,直到全部记录插入完成为止。简单来说就是:取出一个元素,寻找插入位置! 设数组为a[n]。 1.初始时,a[0]看成有序区,无序区为a[1..n-1]。 2.i=1循环到i=n-1,将a[i]并入当前的有序区a[0…i-1]中形成a[0…i]的有序区间。排序完成。 代码如下:(由小到大排序) [cpp] void Insertso...

快速排序(分治)

快速排序(分治)
注:本站的大多数算法为本人手打,如果该算法有错误,或阅者有更好的代码优化建议,请评论!将立即修改! 分治快速排序 由著名的计算机科学家霍尔给出的快速分类算法,不同于归并,取一个元素值作为划分值,元素小的直接靠前,元素大的直接靠后。强于归并。 时间复杂度 事实上,在快速算法中最坏的情况下,划分元素总是最大或最小的元素,快排算法中会退化成冒泡,即:O(n^2),但我们考虑的是平均复杂度O(nlo...

白话经典算法系列之一 冒泡排序的三种实现

白话经典算法系列之一 冒泡排序的三种实现
在CSDN看到的白话算法,不错,认真阅读了一边感觉有用,修改和完善了部分代码,版权为:MoreWindows,如果作者不希望本站转载,发EMAIL致10814750#qq.com,谢谢! 冒泡排序是非常容易理解和实现,,以从小到大排序举例: 设数组长度为N。 1.比较相邻的前后二个数据,如果前面数据大于后面的数据,就将二个数据交换。 2.这样对数组的第0个数据到N-1个数据进行一次遍历后,最大的一个数据就“沉”到数组第N-1个...

归并排序(分治)

归并排序(分治)
归并排序,模型如下: if low<high then mid<-[n/2] call mergesort(low,mid); call mergesort(mid+1,high); call merge(low,mid,high); endif end mergesort 示例程序: [cpp] #include <iostream> using namespace std; long long cnt; int a[1000010]; void merge(int s1,int e1,int s2,int e2) { int p1=s1,p2=s2,p=0,*t; t=new int[e2-s1+5]; while(p1<=e1&&p2<=e2) { if(a[p...

分治法

分治法
道家:"一生二,二生三,三生万物!"--《道德经》 分治二分检索 [cpp] //二分检索算法,查找元素520是否在数列中,是'YES',否'NO'; #include <iostream> using namespace std; int main() { int n,*p; cout<<"输入元素个数:";cin>>n; p=new int[n]; for(int i=0;i<n;i++) cin>>p[i]; int low=0,high=n-1,mid,number=0; while(low<=high) { mid=(low+high)/2; if(p[mid]<520) l...
Copyright © C/C++程序员之家 保留所有权利.   Theme  Ality 浙ICP备15011757号-3

用户登录