首页 > 代码库 > 贪心2--均分纸牌

贪心2--均分纸牌

贪心2--均分纸牌

一、心得

 

二、题目及分析

 

贪心法:

贪?算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。

贪心算法不是对所有问题都能得到整体最优解,关键是贪?心策略的选择,选择的贪?策略必须具备?后效性,即某个状态以后的过程不会影响以前的状态,只与当前状态有关。

太概念化了。总结起来三点:

可行性:必须满足问题的约束

局部最优:当前步骤中所有可行的选择里最佳的局部选择。

不可取消:选择一旦做出,后面的步骤就无法改变。

问题要具有贪心选择性:问题的最优解可以通过一系列的局部最优选择来达到。(最重要的一步,决定这个问题是否可以用贪心法来解决,此处的解决特指找到最优解)。

最优子结构性质:指一个问题的最优解一定要包含子问题的最优解。

贪心和DP的差别在哪呢,首先他萌确实都有最优子结构的性质,但是DP通常是以自底向上的方式解决各个子问题(如22中的整装待发问题就是从底部的每一层逐渐建立起那个二维数组),而贪心的方法通常是自顶向上的。

 

均分纸牌问题的分析:

均分纸牌问题:有 N 堆纸牌,编号分别为 1,2,…, N。每堆上有若干张,但纸牌总数必为 N 的倍数。可以在任一堆上取若于张纸牌,然后移动。

  移牌规则为:在编号为 1 堆上取的纸牌,只能移到编号为 2 的堆上;在编号为 N 的堆上取的纸牌,只能移到编号为 N-1 的堆上;其他堆上取的纸牌,可以移到相邻左边或右边的堆上。

  现在要求找出一种移动方法,用最少的移动次数使每堆上纸牌数都一样多。

  例如 N=4,4 堆纸牌数分别为:

  ① 9 ② 8 ③ 17 ④ 6

  移动3次可达到目的:

  从 ③ 取 4 张牌放到 ④ (9 8 13 10) -> 从 ③ 取 3 张牌放到 ②(9 11 10 10)-> 从 ② 取 1 张牌放到①(10 10 10 10)。

三、代码及结果

 

 1 #include <iostream>
 2 using namespace std;
 3 int main(){
 4     int n;
 5     int a[105];
 6     cin>>n;
 7     int sum=0;
 8     for(int i=1;i<=n;i++){
 9         cin>>a[i];
10         sum+=a[i];
11     }
12     int ave=sum/n;
13     for(int i=1;i<=n;i++){
14         a[i]-=ave;
15     }
16     int i=1,j=n;
17     while(!a[i]) i++;
18     while(!a[j]) j--;
19     int step=0;
20     while(i<j){
21         a[i+1]+=a[i];
22         a[i]=0;
23         step++;
24         while(!a[i]) i++;
25     }
26     cout<<step<<endl;
27     return 0;
28 } 

技术分享

贪心2--均分纸牌