精华内容
下载资源
问答
  • 在刷题时,总会遇到求最大最小,最小值最大问题,也许它会暗喻是这样的一个问题。对于这样的一个问题,你会发现用dp和枚举都会超时超内存,或者说很麻烦,所以这是一个比较简单的解题方式。 二分逼近思想 •对于...

     

    在刷题时,总会遇到求最大值最小,最小值最大问题,也许它会暗喻是这样的一个问题。对于这样的一个问题,你会发现用dp和枚举都会超时超内存,或者说很麻烦,所以这是一个比较简单的解题方式。

    二分逼近思想

    对于难以直接确定解的问题,采取二分枚举+检验的思想.

    已知解为x,验证x是否满足要求.

    如果答案具有特定的范围,并且验证答案是否成立的函数具有单调性。则可以在范围内对答案进行二分验证,从而快速确定答案。

     对于答案判断:

    在二分答案的时候需要判断,从而确定下一个范围。

    可以用一个bool Check(x)函数来判断,返回true表示满足,返回false表示不满足.

    可以类比数学函数f(x)>=0f(x)<0来理解.

    根据具体问题写出相应的Check函数往往就是解决问题的关键点。

    下面举例一些问题:

    poj2456

    Aggressive cows

    Time Limit: 1000MS Memory Limit: 65536K
    Total Submissions: 13139 Accepted: 6399

     

    Description

    Farmer John has built a new long barn, with N (2 <= N <= 100,000) stalls. The stalls are located along a straight line at positions x1,...,xN (0 <= xi <= 1,000,000,000). 

    His C (2 <= C <= N) cows don't like this barn layout and become aggressive towards each other once put into a stall. To prevent the cows from hurting each other, FJ want to assign the cows to the stalls, such that the minimum distance between any two of them is as large as possible. What is the largest minimum distance?

    Input

    * Line 1: Two space-separated integers: N and C 

    * Lines 2..N+1: Line i+1 contains an integer stall location, xi

    Output

    * Line 1: One integer: the largest minimum distance

    Sample Input

    5 3
    1
    2
    8
    4
    9

    Sample Output

    3

    Hint

    OUTPUT DETAILS: 

    FJ can put his 3 cows in the stalls at positions 1, 4 and 8, resulting in a minimum distance of 3. 

    Huge input data,scanf is recommended.

    Source

    USACO 2005 February Gold

     

    2.题意概述:

    农夫有c头牛,n个隔间,c头牛很躁动,很容易相互打架,因此农夫想把它们分得越远越好,要你分配隔间使得相邻两头牛的距离越远越好,问你这c头牛分割的最小距离的最大值。

    3.解题思路: 

    先对隔间的坐标排序,对于牛,最小距离是0,最大距离不会超过两端两头牛的距离值,因此二分地查找分割距离的最大值,每次mid都judge一次,judge的时候贪心地放置牛,保证前i头牛是符合这样分割标准的。

    AC代码:

     

    #include<iostream>
    #include<algorithm>
    using namespace std;
    	int n,k,t;
    	int a[100000];
    bool fun(int d){
    	int next,last=0,k=1;
    	for(int i=1;i<t;i++){
    		if(a[i]-a[last]>=d){
    			k++;
    			last=i;
    		}
    	}
    	if(k>=n)
    		return true;
    	else
    		return false;
    }
    int main(){
    cin>>t;
    cin>>n;
    	for(int i=0;i<t;i++)
    		cin>>a[i];
    	sort(a,a+t);
    	int l=0,r=a[t-1],mid=(l+r)/2;
    	while(l<=r){
    		if(fun(mid)){
    			l=mid+1;
    		}
    		else{
    			r=mid-1;	
    		}
    		mid=(l+r)/2;
    	
    	}
    	cout<<r<<endl;
    	return 0;
    } 

     

     

     

     

     

    poj1505 

    Copying Books

    Time Limit: 3000MS Memory Limit: 10000K
    Total Submissions: 9632 Accepted: 3013

    Description

    Before the invention of book-printing, it was very hard to make a copy of a book. All the contents had to be re-written by hand by so called scribers. The scriber had been given a book and after several months he finished its copy. One of the most famous scribers lived in the 15th century and his name was Xaverius Endricus Remius Ontius Xendrianus (Xerox). Anyway, the work was very annoying and boring. And the only way to speed it up was to hire more scribers. 

    Once upon a time, there was a theater ensemble that wanted to play famous Antique Tragedies. The scripts of these plays were divided into many books and actors needed more copies of them, of course. So they hired many scribers to make copies of these books. Imagine you have m books (numbered 1, 2 ... m) that may have different number of pages (p1, p2 ... pm) and you want to make one copy of each of them. Your task is to divide these books among k scribes, k <= m. Each book can be assigned to a single scriber only, and every scriber must get a continuous sequence of books. That means, there exists an increasing succession of numbers 0 = b0 < b1 < b2, ... < bk-1 <= bk = m such that i-th scriber gets a sequence of books with numbers between bi-1+1 and bi. The time needed to make a copy of all the books is determined by the scriber who was assigned the most work. Therefore, our goal is to minimize the maximum number of pages assigned to a single scriber. Your task is to find the optimal assignment. 

    Input

    The input consists of N cases. The first line of the input contains only positive integer N. Then follow the cases. Each case consists of exactly two lines. At the first line, there are two integers m and k, 1 <= k <= m <= 500. At the second line, there are integers p1, p2, ... pm separated by spaces. All these values are positive and less than 10000000.

    Output

    For each case, print exactly one line. The line must contain the input succession p1, p2, ... pm divided into exactly k parts such that the maximum sum of a single part should be as small as possible. Use the slash character ('/') to separate the parts. There must be exactly one space character between any two successive numbers and between the number and the slash. 

    If there is more than one solution, print the one that minimizes the work assigned to the first scriber, then to the second scriber etc. But each scriber must be assigned at least one book.

    Sample Input

    2
    9 3
    100 200 300 400 500 600 700 800 900
    5 4
    100 100 100 100 100

    Sample Output

    100 200 300 400 500 / 600 700 / 800 900
    100 / 100 / 100 / 100 100

     

    题意:按顺序给你N个数,将这N个数分成连续的M段,使得这M段每段的和中的最大值最小,输出最小值(1<=N<=100000,1<=M<=N,每个数在1到10000之间),如果有多种可能的话,尽量在前面进行划分。(其实第一次读题还不知道是什么意思,仔细琢磨才明白是这样的一个问题)

    首先以正常的思路去考虑优化这个最大值的最小化问题,好像会陷入到循环之中找不到解决的思路,但是我们如果采用猜测-判断-重来的方法不断的去尝试二分查找最大值的最小值,然后去判断这个值是否合法,进一步优化这个值,就可以解决。

    ac代码:

    #include<iostream>
    using namespace std;
    int a[501];
    int t,m,n;
    int yes_no(int dis,int flag){
    	int last=0,next=0,tsum=a[last],cnt=1;
    	while(next<m){
    		if(tsum<=dis){
    			next++;
    			tsum=tsum+a[next];
    		}
    		if(tsum>dis){
    			cnt++;
    			last=next;
    			tsum=a[last];
    		}
    		
    	}
    //	cout<<cnt<<endl;
    	if(cnt>flag)
    		return 2;
    	else if(cnt==flag)
    		return 1;
    	else
    		return 0;
    }
    int main(){
    	cin>>t;
    	while(t--){
    		int sum=0,ans;
    		cin>>m>>n;
    		for(int i=0;i<m;i++){
    			cin>>a[i];
    			sum+=a[i];
    		}
    		//cout<<sum<<endl;
    		int l=0,r=sum,mid;
    		//cout<<mid<<endl;	
    		while(l<=r){
    			mid=(l+r)>>1;
    			if(yes_no(mid,n)==2){
    				l=mid+1;
    				//cout<<"1";
    			}
    			else if(yes_no(mid,n)==1){
    				ans=mid;
    				r=mid-1;
    			}
    			else{
    				r=mid-1;
    			//	cout<<"2";
    			}
    		}
    		//cout<<ans<<endl;
    		int tsum=0;
    		int tn=n-1;
    		for(int i=0;i<m;i++){
    			tsum+=a[i];
    			if(tsum>=ans&&tn){
    				tn--;
    				cout<<" /";
    				tsum=a[i];
    			}
    			if(i==0){
    				cout<<a[i];
    			}
    			else
    				cout<<" "<<a[i];				
    		}	cout<<endl;	
    	}
    	
    } 

    以上就是这两题,是基本的贪心+二分的求法。 

    注意:二分是在排序好的基础上进行的查找,所以,看清题目,尽量先排好序。。。

    展开全文
  • 经典贪心最大延时最小问题问题描述贪心方法试探短作业优先的尝试证明短作业优先的构造反例研究从反例不等式组推正确的贪心方法期限早优先法的证明 问题描述 贪心方法试探 首先可以想到一些贪心方法,比如按执行...

    问题描述

    在这里插入图片描述

    贪心方法试探

    首先可以想到一些贪心方法,比如按执行时间排序做短作业优先的过程。我们分析它行不行,即尝试证明这种方法。

    短作业优先的尝试证明

    假设求出的处理序列有相邻两项 p r o j e c t i project_i projecti p r o j e c t i + 1 project_{i+1} projecti+1,按照约定, t i < t i + 1 t_i<t_{i+1} ti<ti+1。这两项交换不会影响其他项,所以只考虑这两项对自己的影响:
    原来的延时二元组是 ( s u m + t i − d i , s u m + t i + t i + 1 − d i + 1 ) (sum+t_i-d_i ,\quad sum+t_{i}+t_{i+1}-d_{i+1}) (sum+tidi,sum+ti+ti+1di+1)
    交换后的延时二元组是 ( s u m + t i + 1 − d i + 1 , s u m + t i + t i + 1 − d i ) (sum+t_{i+1}-d_{i+1} ,\quad sum+t_i+t_{i+1}-d_i) (sum+ti+1di+1,sum+ti+ti+1di)
    其中 s u m = ∑ k = 1 i − 1 t k sum=\sum_{k=1}^{i-1}t_k sum=k=1i1tk
    但是每个数都加了sum,因为只研究大小关系,sum早晚会消掉,可以忽略。
    那么能否证明 m a x ( t i − d i , t i + t i + 1 − d i + 1 ) ⩽ m a x ( t i + 1 − d i + 1 , t i + t i + 1 − d i ) max(t_i-d_i ,\quad t_{i}+t_{i+1}-d_{i+1}) \leqslant max(t_{i+1}-d_{i+1} ,\quad t_i+t_{i+1}-d_i) max(tidi,ti+ti+1di+1)max(ti+1di+1,ti+ti+1di)
    从而证明这种贪心的正确性呢?
    很不幸,不能。可以想办法构造反例。

    短作业优先的构造反例研究

    如果能够造两个项目满足下面不等式组 { t i + t i + 1 − d i + 1 ⩾ t i − d i t i + t i + 1 − d i ⩽ t i + 1 − d i + 1 t i ⩽ t i + 1 ( 约 定 条 件 ) t i + t i + 1 − d i + 1 ⩾ t i + 1 − d i + 1 ( t i 非 负 自 然 满 足 ) \left\{ \begin{array}{l} t_{i}+t_{i+1}-d_{i+1} \geqslant t_i-d_i\\\\ t_i+t_{i+1}-d_i \leqslant t_{i+1}-d_{i+1}\\\\ t_i \leqslant t_{i+1}(约定条件)\\\\ t_{i}+t_{i+1}-d_{i+1} \geqslant t_{i+1}-d_{i+1}(t_i非负自然满足) \end{array} \right. ti+ti+1di+1tiditi+ti+1diti+1di+1titi+1()ti+ti+1di+1ti+1di+1(ti)
    的话,那原来的答案延时 t i + t i + 1 − d i + 1 t_{i}+t_{i+1}-d_{i+1} ti+ti+1di+1 就会变成 t i + 1 − d i + 1 t_{i+1}-d_{i+1} ti+1di+1,从而变小。这样这种短作业优先的方法就不是最优的。
    比如t1=1,d1=100,t2=2,d2=2这个样例就满足上面的不等式组,从而形成反例。

    从反例不等式组推正确的贪心方法

    如何让上面的反例不等式组无论如何也不可能满足呢?很自然发现只要保证 d i < d i + 1 d_i<d_{i+1} di<di+1就行。

    期限早优先法的证明

    通过上面的推算已经能猜出这种改进方法八九不离十是对的,即按这种办法排序后,交换两项后答案不可能变小。
    同样考虑相邻两项:
    即能否证明 m a x ( t i − d i , t i + t i + 1 − d i + 1 ) ⩽ m a x ( t i + 1 − d i + 1 , t i + t i + 1 − d i ) w h e n d i ⩽ d i + 1 max(t_i-d_i ,\quad t_{i}+t_{i+1}-d_{i+1}) \leqslant max(t_{i+1}-d_{i+1} ,\quad t_i+t_{i+1}-d_i)\\when \quad d_i \leqslant d_{i+1} max(tidi,ti+ti+1di+1)max(ti+1di+1,ti+ti+1di)whendidi+1
    显然是可以的,因为此时一定存在
    { t i + t i + 1 − d i ⩾ t i − d i t i + t i + 1 − d i ⩾ t i + t i + 1 − d i + 1 m a x ( t i + 1 − d i + 1 , t i + t i + 1 − d i ) ⩾ t i + t i + 1 − d i \left\{ \begin{array}{l} t_i+t_{i+1}-d_i \geqslant t_i-d_i\\\\ t_i+t_{i+1}-d_i \geqslant t_{i}+t_{i+1}-d_{i+1}\\\\ max(t_{i+1}-d_{i+1} ,\quad t_i+t_{i+1}-d_i) \geqslant t_i+t_{i+1}-d_i \end{array} \right. ti+ti+1ditiditi+ti+1diti+ti+1di+1max(ti+1di+1,ti+ti+1di)ti+ti+1di
    所以交换一定不会让答案变小。
    而且任何不安这种贪心的顺序的序列都能一步一步相邻两个符合次序的相邻对交换为逆序相邻对得到,就像冒泡排序。所以答案会随着这样的交换一点点变大。所以这种 期限早优先法是对的。
    这就是证明过程。

    展开全文
  • = m),在这 n 个可选位置中选择 m 个建加油站有很多种方式,每一种方式中,两个相邻加油站之间的距离都有一个最小值,每种情况的最小距离可能不一样,问所有情况中,这个最小距离的最大值是多少? 2 <= n, m <...

    有一条高速公路,想要建设 m 个加油站,一共有 n 个可以选择建设加油站的地点(n >= m),在这 n 个可选位置中选择 m 个建加油站有很多种方式,每一种方式中,两个相邻加油站之间的距离都有一个最小值,每种情况的最小距离可能不一样,问所有情况中,这个最小距离的最大值是多少?
    2 <= n, m <= 100000
    1 <= a[i] < a[i + 1] <= 109 (a[i] 是加油站位置)

      原题不是这样的,但是很多人并没有理解题什么意思(什么是最小距离最大值),所以我就翻译了一下,变成上边这道题。
      输入第一行是 n 和 m,接下来下 n 个数是加油站的位置(保证是递增的,也就是 a[i + 1] > a[i])。比如下边例子:

    Input 1:        Input 1:
    5 3          5 4
    1 4 5 6 9        1 4 5 6 9

    Output 1:       Output 2:
    4 (1 5 9)       2 (1 4 6 9)

      网上很多答案说用 DP,dp[i][j] 表示前 i 个位置中选择 j 个最小距离最大值是多少,但是这道题的 n 和 m 最大都是十万,数组开不了这么大的,vs中开这么大数组直接编译就错了。所以不是 DP,而是二分+贪心

    二分+贪心

      对于这样的最小值最大是多少,或者最大值最小是多少的问题,其实就是对于一个值 m,我们贪心地判断这个 m 满不满足条件,比如最小值最大是多少,我们判断 m 满不满足比所有数都小,满足的话,说明这个最大的最小值肯定 >= m,那就让 m 变大,否则让 m 变小,继续判断。这样就很明确了,对 m 进行二分,每次贪心地判断这个 m 可不可行。AC 100% 的代码如下:

    #include <iostream>
    #include <vector>
    using namespace std;
    
    bool check_dis(int remain_merge_time, const vector<int>& dis, int check_dis) {
    	int i = 0, pre_sum = 0;
    	while (i < dis.size()) {
    		if (dis[i] + pre_sum >= check_dis)
    			pre_sum = 0;
    		else {
    			pre_sum += dis[i];
    			if (remain_merge_time == 0) return false;
    			--remain_merge_time;
    		}
    		++i;
    	}
    	return true;
    }
    
    int main() {
    	int n, m, pre, t, sum = 0;
    	cin >> n >> m >> pre;
    	vector<int> dis;
    	for (int i = 1; i < n; ++i) {
    		cin >> t;
    		sum += t - pre;
    		dis.push_back(t - pre);
    		pre = t;
    	}
    	long long l = 0, r = sum;
    	while (r >= l) {
    		const int mid = l + (r - l) / 2;
    		// 贪心地看 arr 数组能不能合并成每一段都 >= tmp 的数组,只能合并 n - m 次
    		const bool flag = check_dis(n - m, dis, mid);
    		//cout.setf(ios_base::boolalpha);
    		//cout << "mid = " << mid  << ", flag: " << flag << endl;
    		if (flag) l = mid + 1;
    		else      r = mid - 1;
    	}
    	cout << r << endl;
    }
    

      读取的时候,我把 1 4 5 6 9 这样的加油站位置,变成了 3 1 1 3 这样的距离数组,那么要做的就是每次看一个 mid 能不能满足在 n - m 次合并内所有数都 >= m(为什么可以这样,是因为最左边和最右边的加油站一定会选,至于为什么一定会选,想一下就知道了)。比如 n = 5, m = 4,那就是只能合并一次,那就让 1 和 1 合并成为 2,mid 最大就是 2,如果是 n = 5, m = 3,那就可以合并两次,让 3 1 合并成 4,1 3 也合并成 4,mid 最大就是 4。
      主要步骤就是分为两步:
    1、二分:二分过程很简单,下界是 0 或 1 都行,上界其实不是很重要,选一个大点的就行;
    2、贪心:贪心的过程也很容易理解,就是当一个数 < m 的时候,就用掉一次合并,跟它后边的合并,还小就还合并直到 >= m,合并次数为 0 后还需要合并,就说明这个 mid 选大了,如果这个 mid 返回 true,说明可以,让 mid 变大再试试,最后 r < l 的时候跳出 while。比如 2 可以,4 不可以,3 可以,那么 l 从 3 变成 4,r 还是 3,跳出循环,输出 r,也就是3;如果 2 可以,4 不可以,3 不可以,那么 l 还是 3 不变,r 变成 2,跳出 while,输出 r 也就是 2。

      代码中的输出取消注释后,试一下例子1,可以看到:

    展开全文
  • 树上最大独立集,最小支配集,最小覆盖子集(贪心做法)

    含义: 最小支配集:对于图G=(V,E),从V中取尽量少的点,组成V’;对于原图中的任意顶点u,属于集合V‘或者与V‘中的点相连;

                最小覆盖点集:对于图G=(V,E),从V中取尽量少的点,组成V’;对于原图中的任意一条边(u,v),u属于V'或者v属于V';

                最大独立子集:对于图G=(V,E)来说,最大独立集指的是从V中取尽量多的点组成一个集合,使得这些点之间没有边相连。

    首先邻接表存下边,先以任意一个点为根,进行深度遍历,记录每个节点的父节点并得到深度遍历序列;

    #include <iostream>
    #include <string.h>
    using namespace std;
    const int maxn=1e5+10;
    struct point {
    	int next;
    	int to;
    };
    point pt[maxn*2];
    int q,k;
    int head[maxn*2],fa[maxn],sto[maxn];
    bool  dis[maxn],re[maxn],vis[maxn];
    void add(int u,int v)
    {
             pt[q].next=head[u];
    	 pt[q].to=v;
    	 head[u]=q++;	
    } 
    void dfs(int st)
    {
    	for (int i=head[st];i!=-1;i=pt[i].next)
    	{
    		int v=pt[i].to;
    		if (!vis[v])
    		{
    			vis[v]=true;
    			dfs(v);
    			fa[v]=st;
    			sto[k++]=v;
    		}
    	}
    }

    ①最小支配集:按照深度优先进行反向检查,如果当前点不属于支配集也不与支配集中的点相连,如果他的父亲不属于支配集,将其父节点加入支配集,支配集中点的个数加一,标记当前节点,当前节点的父亲节点,当前节点的父亲节点的父亲节点,这些点或者属于支配集,或者与支配集中的点相连;

    int min_zhi()
    {
    	memset(re,false,sizeof(re));
    	memset(dis,false,sizeof(dis));
    	int ans=0;
    	for (int i=0;i<k;i++)
    	{
    		int va=sto[i];
    		if (!dis[va])
    		{
    			if (!re[fa[va]])
    			{
    			 re[fa[va]]=true;
    			 ans++;
    		    }
    		    dis[va]=dis[fa[va]]=dis[fa[fa[va]]]=true;
    		}
    	}
    	return ans;
    }

    ②最小覆盖自子集:如果当前点和当前点的父亲节点都不属于顶点覆盖集合,将其父节点加入到顶点覆盖集合,并标记当前节点和当前节点的父节点;

    int  min_fu()
    {
    	memset(re,false,sizeof(re));
    	memset(dis,false,sizeof(dis));
    	int ans=0;
    	for (int i=0;i<k;i++)
    	{
    		int va=sto[i];
    		if (!dis[va]&&!dis[fa[va]])
    		{
    			re[fa[va]]=true;
    			ans++;
    			dis[va]=dis[fa[va]]=true;
    		}
    	}
    	return ans;
    }

    ③最大独立集:如果当前点没有被覆盖,则加入当前点到独立集中,并标记此节点和其父亲节点都被覆盖;

    int  max_du()
    {
    	memset(re,false,sizeof(re));
    	memset(dis,false,sizeof(dis));
    	int ans=0;
    	for (int i=0;i<k;i++)
    	{
    		int va=sto[i];
    		if (!dis[va])
    		{
    			re[fa[va]]=true;
    			ans++;
    			dis[va]=dis[fa[va]]=true;
    		}
    	}
    	return ans;
    }

    主函数:

    int main()
    {
    	int n,m,u,v;
         while (scanf("%d%d",&n,&m))
         {
         	memset(head,-1,sizeof(head));
         	q=1,k=0;
         	for (int i=0;i<m;i++)
         	{
         		scanf("%d%d",&u,&v);
         		add(u,v);
         		add(v,u);
    		}
    		memset(vis,false,sizeof(vis));
    		vis[1]=true;
    		fa[1]=1; (设1为根节点)
    		dfs(1);
    		for (int i=0;i<k;i++)
    		cout<<sto[i]<<"***";
    		cout<<endl;
    		for (int i=1;i<=10;i++)
    		cout<<fa[i]<<" ";
    		cout<<endl;
    		printf("%d\n",min_zhi());
    		for (int i=1;i<=10;i++)
    		cout<<re[i]<<" ";
    		cout<<endl;
    		printf("%d\n",min_fu());
    		for (int i=1;i<=10;i++)
    		cout<<re[i]<<" ";
    		cout<<endl;
    		printf("%d\n",max_du());
    		for (int i=1;i<=10;i++)
    		cout<<re[i]<<" ";
    		cout<<endl;
    	 }
    	 return 0;
    } 





    展开全文
  • 无线传感器网络的最大干扰最小化问题可以被描述为已知平面上<i>n个点的位置及发射半径的阈值,要求设置发射半径使得任意点被其他点发射范围覆盖的最大数量达到最小。为了有效求解该问题,提出了一种新的贪心算法——...
  • 最小生成树——贪心算法

    千次阅读 多人点赞 2019-03-19 21:25:59
    生成树和最小生成树1.1 问题的定义1.2 MST性质2.普里姆算法(Prim)2.1 算法流程2.2 算法正确性证明2.3 算法实现2.4 测试代码3.克鲁斯卡尔算法 1.生成树和最小生成树 1.1 问题的定义 一个连通图 的生成树是一个极小...
  • 最小支配集(minimal dominating set):对于图G=(V,E)来说,设V'是图G的一个支配集,则对于图中的任意一个顶点u,要么属于集合V',要么与V'中的顶点相连。 在V'中除去任何元素后V'不再是支配集,则支配集V'是极小...
  • 问题描述 已知一个正整数N,问从1~N中任选出三个数,他们的最小公倍数最大可以为多少。 ...输出一个整数,表示你找到的...当时不知道该怎么使用贪心算法,也不知道怎么贪心,因为题目最大最小公倍数“可能“是
  • 最小支配集:对于图G = (V, E) 来说,最小支配集指的是从 V 中取尽量少的点组成一个集合, 使得 V 中剩余的点都与取出来的点有边相连.也就是说,设 V' 是图的一个支配集,则对于图中的任意一个顶点 u ,要么属于集合 V', ...
  • 1.贪心算法求解最小生成树问题: 要求:分别用c/c++实现prim算法和Kruskal算法求解一个网络的最小生成树; 分析两种算法的时间复杂度和各自的特点 2.代码: //c实现prim算法源代码: #include <stdio.h> #...
  • 要求:尽可能让装入背包中的物品总价值最大,但前提条件是:不能超过总容量150kg。 8件物品的标号、重量、价值如下表所示: 物品 重量 价值 1 35kg 10 2 30kg 40 3 6kg 30 4 50kg 50 5 40kg 35 6 10kg 40 7 25kg 30...
  • 最大权值最小 生成树

    2011-05-30 21:23:08
    最大权值最小生成树 贪心算法实现。。。。。。。。。。。。。。。。。。。。。。。。。。
  • 问题描述已知一个正整数N,问从1~N中任选出三个数,他们的最小公倍数最大可以为多少。输入格式输入一个正整数N。输出格式输出一个整数,表示你找到的最小公倍数。样例输入9样例输出504数据规模与约定1 &lt;= N &...
  • 算法训练 最大最小公倍数 简单贪心算法

    千次阅读 多人点赞 2015-02-05 21:56:19
    算法训练 最大最小公倍数 时间限制:1.0s 内存限制:256.0MB 问题描述 已知一个正整数N,问从1~N中任选出三个数,他们的最小公倍数最大可以为多少。 输入格式 输入一个正整数N。 ...
  • 贪心算法之最小堆实现霍夫曼编码

    千次阅读 2016-10-11 22:22:29
    贪心算法之最小堆实现霍夫曼编码 实现之前需要学习的地方: 如果你不了解堆、堆的插入、堆的删除,可以先看下我前面几篇博客 http://blog.csdn.net/u011068702/article/details/52712634最详细的最小堆构建、插入、...
  • 目标:设计一种安排策略最小最大延迟,即 L = m a x j l j L =max_j{l_j} L = m a x j ​ l j ​ 正确的贪心策略 按照到期时间从早到晚进行排序,然后无间隙执行,得到的就是最优解 下图就是贪心安排的一个图...
  • 在用贪心法解决最小顶点覆盖问题中,它贪的是覆盖的边最多的顶点。用邻接矩阵存储无向图,矩阵中每行的和即为顶点的出度。出度最多的顶点即为最优量度标准。 最小顶点覆盖其一般特性: (1)找覆盖边最多的顶点 (2)已...
  • 贪心算法----最小差值

    2019-04-07 18:09:43
    没做出来,看了老哥们的题解才恍然大悟 ...返回 B 的最大值和 B 的最小值之间可能存在的最小差值。 示例 1: 输入:A = [1], K = 0 输出:0 解释:B = [1] 示例 2: 输入:A = [0,10], K = 2 输出:...
  • 贪心算法 -- 最小延迟调度

    千次阅读 2018-10-31 13:25:34
     首先,证明贪心的时候交换论证是万能的!其次,这一点如果要满足,也就是,如果你要用交换论证法,那么首先要保证交换逆序后,对其他的没有影响!如果有影响,那就只能像【POJ - 3253】Fence Repair 这道题一样,...
  • 已知一个正整数N,问从1~N中任选出三个数,他们的最小公倍数最大可以为多少。 输入格式 输入一个正整数N。 输出格式 输出一个整数,表示你找到的最小公倍数。 样例输入 9 样例输出 504 数据规模与约定 1 <= N <...
  • C++贪心算法之最小新整数

    千次阅读 2017-08-18 13:21:23
    最小新整数 Description 给定一个十进制正整数n(0 现在从m位中删除k位(0 例如: n = 9128456, k = 2, 则生成的新整数最小为12456 Input 第一行t, 表示有t组数据; 接下来t行,每一行表示一组测试数据,...
  • 最小延迟调度问题——贪心算法(C++实现)

    千次阅读 多人点赞 2020-05-04 09:56:21
    1.最小延迟调度问题描述 f(i) 表示某任务 开始的时间。 ti 表示 某任务 加工的时间 di 表示 某任务 要求完成的时间 延迟: f(i)+ti-di 如果 实际完成的时间 小于 规定完成时间,那么,就没有 延迟。延迟就是...
  • 使用贪心算法解决最小生成树

    千次阅读 2019-01-06 14:56:37
    最小生成树(MST Minimun spanning tree):给定图G(V,E),以及对应的边的权重,获取一颗总权重最小的生成树。 树的定义:连接的无环图 直接策略 找到所有的生成树,然后计算权重最小的 考虑上面的图,一但红色线选定...
  • 上一篇主要介绍了贪心算法的内容和活动选择问题。本篇主要介绍最优装载问题和最小延迟调度问题 1、最优装载问题 什么是最优装载问题 类似于0-1背包问题那样,有n个集装箱1,2,…,n装上轮船,集装箱i的质量wi,轮船...
  • 贪心最大整数

    千次阅读 2018-04-19 10:55:27
    描述设有n(n≤20)个正整数(每个在int范围内),将它们连接成一排,组成一个最大的多位整数。...7 13 4 246样例输出7424613提示贪心解题思路 使用贪心思想,首先把每两个数进行一次组合,把组合...
  • 蓝桥杯——最大最小公倍数

    千次阅读 多人点赞 2019-03-20 20:24:32
    算法训练 最大最小公倍数 问题描述:   已知一个正整数N,问从1~N中任选出三个数,他们的最小公倍数最大可以为多少。 输入格式:   输入一个正整数N。 样例输入:   9 样例输出:   504 数据规模与约定  ...
  • 已知一个正整数N,问从1~N中任选出三个数,他们的最小公倍数最大可以为多少。 输入格式 输入一个正整数N。 输出格式 输出一个整数,表示你找到的最小公倍数。 样例输入 9 样例输出 504 思路: 这是一个简单的贪心...
  •  详细实现请点击查看  书本内容(因为我在博客中别的地方已经实现故直接给出链接):                
  • 贪心算法设计策略设计出构造最小生成树的有效算法krukal算法实现C语言
  • 最大最小公倍数 C语言 问题描述 已知一个正整数N,问从1~N中任选出三个数,他们的最小公倍数最大可以为多少。 输入格式 输入一个正整数N。 输出格式 输出一个整数,表示你找到的最小公倍数。 样例输入 9 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 44,511
精华内容 17,804
关键字:

最大加最小贪心