动态规划之合唱队形问题
动态规划之合唱队形问题
一贱书生 发表于1年前
动态规划之合唱队形问题
  • 发表于 1年前
  • 阅读 10
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云 新注册用户 域名抢购1元起>>>   

问题描述:

  N 位同学站成一排,音乐老师要请其中的(N-K)位同学出列,而不改变其他同学的位置,使得剩下的K位同学排成合唱队形。合唱队形要求:设K位同学从左到右 依次编号为1,2…,K,他们的身高分别为T1,T2,…,TK,则他们的身高满足 T1<T2...<Ti>Ti+1>…>TK(1<=i<=K)。已知所有N位同学的身高,计算最少需要几位 同学出列,可以使得剩下的同学排成最长的合唱队形。 

问题分析:

  假设第i位同学为个子最高的同学,我们先对其左边的同学求最大上升子序列,再对其右边的同学求最大下降子序列,然后两者相加再减1(第i位同学被重复计算 了一次),便得到第i位同学为最高个时所能排成的最长合唱队形。如果我们对这N位同学都执行此操作,便可得到每位同学为最高个时所能排成的最长合唱队形, 选取其中最长的合唱队形作为最终的结果。  

 从 上述的分析可以看出,我们可以将问题分成互相不独立的子问题,只要得到子问题的最优解,便可得到整个问题的最优解。我们可以用一张表来记录所有已解决问题 的答案,从而避免了重复计算。这里的一个关键问题便是:如何得到第i位同学的最大上升子序列和最大下降子序列。假如这N位同学的身高分别 为:176,163,150,180,170,130,167,160,我们用up[i]来记录第i位同学的最大上升子序列。如果要得到180同学为最高 个时的最大上升子序列即up[4],我们只需求出前3位同学所能形成的最大上升子序列,将其加1即可;要得到前3位同学所形成的最大上升子序列,便要求得 前2位同学的最大上升子序列,再加上1即可;同样要得到前2位同学的最大上升子序列,便要求得第1位同学的最大上升子序列。因此这是一个递推关系,只要我 们将前i个同学为最高个时做形成的最大上升子序列的值记录下来,取其中最大值加1便可得到第i位同学的最大上升子序列即up[i]。同理我们用 down[i]来记录第i位同学的最大下降子序列,只要我们将后(N-i)位同学每位同学为最高个时的最大下降子序列记录下来,取其中最大者再加1便可得 到第i位同学为最高个时的最大下降子序列即down[i]。那么,第i位同学为最高个时做能形成的最长合唱队形的长度为up[i]+down[i]-1。 求得所有同学为最高个时所能形成的最长合唱队形的长度,取其中最大值为最终的结果。

[java] view plain copy

 

  1. public class Main {  
  2.     public static void main(String[] args) {  
  3.         int []high={176,163,150,180,170,130,167,160};  
  4.         int []up=new int[8];   //记录每位同学的最大上升子序列  
  5.         int []down=new int[8]; //记录每位同学的最大下降子序列  
  6.         for(int i=0;i<high.length;i++){  
  7.             up[i]=1; //每位同学的最大上升子序列初始值为1  
  8.             for(int j=0;j<i;j++){  
  9.                 if((high[j]<high[i])&&(up[i]<up[j]+1)) up[i]=up[j]+1; //前i位同学的最大上升子序列的最大值再加1  
  10.             }  
  11.         }  
  12.         for(int i=high.length-1;i>=0;i--){  
  13.             down[i]=1;  
  14.             for(int j=high.length-1;j>i;j--){  
  15.                 if((high[j]<high[i])&&(down[i]<down[j]+1)) down[i]=down[j]+1; //后N-i位同学的最大下降子序列的最大值再加1  
  16.             }  
  17.         }  
  18.         int max=0; //设每位同学所形成的最长合唱队形的最大值初值为0  
  19.         int index=0; //设最大值对应的索引为0  
  20.         for(int i=0;i<high.length;i++){  
  21.             if(up[i]+down[i]-1>max) {  
  22.                 max=up[i]+down[i]-1; //求得每位同学所形成的最长合唱队形的最大值  
  23.                 index=i;  //求得对应的索引  
  24.             }  
  25.         }  
  26.         System.out.println("最长合唱队形的长度为:"+max);  
  27.         System.out.println("对应的是第"+(index+1)+"位同学,需要"+(high.length-max)+"位同学出列");  
  28.   
  29.     }  
  30. }
共有 人打赏支持
粉丝 15
博文 722
码字总数 600072
×
一贱书生
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: