Java-求最大值问题[比较有挑战]

意见反馈 意见反馈 主题:991 回复:2082

Java-求最大值问题[比较有挑战]

偏爱自由 发布于 2017-09-05 字数 417 浏览 1273 回复 2

对不起,实在不知道取个什么样的名字合适。但这个题感觉真的比较难。

问题如下:
有 n 个无重复随机正整数数,从中取出m个 (m<[n/2]), 要求
1.在这m个数中的任意两个j%i(求余)+ (int)j/i (j/i 取整) 之和为偶数(i,j,i<j) ,
2.对这m个数求和,和要最大。请求出和最大的一组满足要求1的m个数。

请给出比较高效的算法,穷举是不行的。因为在n中取m个数的组合本身已经很大,特别当n和m都比教大的时候。

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

支持 Markdown 语法,需要帮助?

评论(2

灵芸 2017-10-08 2 楼

一、
如果n是具有最大范围的随机数数列,不妨找出该范围内所有符合的数构成映射表,并将该映射表写入文件,或者序列化。以方便查找。
这是没有按规律查找的方法

import java.util.*;
/**

  • @author Administrator
  • 要使得m最大,m必须是同偶数或前一个数是奇数后面都是偶数
    */
    public class Test
    {
    public static boolean Right(int index,List<Integer> m)
    {
    for(int i=0;i<m.size();i++)
    {
    int g=m.get(i);
    int n=g%index+g/index;
    if(n%2==1)
    return false;
    }
    return true;
    }
    public static void main(String args[])
    {
    List<Integer> list=new ArrayList<Integer>();
    List<Integer> m=new ArrayList<Integer>();//数列m
    for(int i=1;i<=1024;i++)
    list.add(i);
    Collections.sort(list);//算法需要,这里必须写上
    int p=2;//游标,由于是有序移动,所以没有必要用remove方法
    int N=list.size();
    int max=list.get(list.size()-1);
    m.add(max);
    if(max%2==1)
    for(int i=N-p;i>=0;i--)
    {
    int n=list.get(i);
    if(n%2==0) {max=n;m.add(n);break;}
    p++;
    }
    //经过试验考证,不难从中发现一个规律,要使得j+i最大,当j为偶数时,那么i必须是j的偶数
    //但j为奇数时,i就必须是j的次偶数
    while((p<=list.size())&&(m.size()<N/2))
    {
    boolean b=false;
    for(int i=list.size()-p;i>=0;i--)
    {
    int n=list.get(i);
    if(n==1)//j=1时无法取得合适的i
    b=true;
    if(n%2==0)//先判断是偶数还是偶数,然后再判断符不符合要求,这样可以减少遍历m的次数
    {
    if(Test.Right(n, m))
    {
    m.add(n);
    p++;
    break;
    }
    }
    p++;
    }
    if(b)break;
    }
    //打印
    for(int i=0;i<m.size();i++)
    {
    h+=m.get(i);
    System.out.println(m.get(i));
    }
    }
    }

次偶数指的是:在一定范围下取得最大的那个偶数
规律我说下吧,因为要分很多种情况,虽然遍历的次数很少,但实现起来很复杂

  1. 当N为奇数数列时,m的最大数列为N的最大值(因为j为奇数的时候,i必为偶数)
  2. 当N为偶数数列时,m最大数列为{N的最大值,小于等于N/2次偶数,小于等于N/2/2的次偶数.....}
  3. 当N为奇数偶数列时,分两种情况:
  4. N的最大值为偶数时,如2的做法可得m最大数列
  5. N的最大值为奇数时,亦分两种情况:一种是选取N最大值max的次偶数,按2做法所组成的数列。第二种是查找max的次偶数,以max和max的次偶数组成一个数列m。
  6. 计N的最小值为min,最大值为max,当max的次偶数大于2的(log2(max)的整数部分)的次方且min<(log2(max)的整数部分)的次方时,第一种情况最大,反之,第二种情况最大
虐人心 2017-09-11 1 楼

我觉得解题的关键条件是: 任意两个j%i(求余)为偶数(i,j,i<j) ;
我从这句话得到的信息是,每一组数都是同奇偶性的数(全偶数、全奇数)!

所以我的思路是,将N长度的无重复数的数组拆分为两个集合!判断两个集合中数字和较大的一组则为正解!

以下是我的java代码,若有不合理的欢迎纠正!

public class Test09 {
/**

  • @param args
    */
    public static void main( String args[] ) {
    int nums[] = { 2 , 6 , 8 , 12 , 56 , 9 , 32 , 47 , 5 , 16 }; // 例子 有n个无重复数的数组
    int len = nums.length;
    List< Integer > oddList = new ArrayList< Integer >();
    List< Integer > evenList = new ArrayList< Integer >();
    for ( int i = 0 ; i < len ; i++ ) { // 将n个数按奇偶性查分
    if ( isEven( nums[ i ] ) ) {
    evenList.add( nums[ i ] ); // 偶数聚集地
    } else {
    oddList.add( nums[ i ] ); // 奇数聚集地
    }
    }
    List< Integer > bigList = isBig( group( oddList , len ) , group( evenList , len ) );
    System.out.println( bigList );
    }
/**
 * 获取两个集合中总和较大的一组
 * 
 * @param oddList
 * @param evenList
 * @return
 */
public static List&lt; Integer &gt; isBig( List&lt; Integer &gt; oddList , List&lt; Integer &gt; evenList ) {
    return sum( oddList ) &gt; sum( evenList ) ? oddList : evenList;
}

/**
 * 得到有效集合
 * 
 * @param list
 * @param len
 * @return
 */
public static List&lt; Integer &gt; group( List&lt; Integer &gt; list , int len ) {
    if ( list.size() &lt; len / 2 ) { // 集合的个数必须为 &lt; n/2
        return list;
    } else {
        Collections.sort( list );
        int size = list.size();
        // 当集合长度大于 n/2 时删除集合中较小的
        for ( int i = size - len / 2 ; i &gt; 0 ; i-- ) {
            list.remove( i - 1 );
        }
        return list;
    }
}

private static int sum( List&lt; Integer &gt; list ) {
    int count = 0;
    for ( Integer integer : list ) {
        count += integer;
    }
    return count;
}

// 判断一个数是否为偶数
private static boolean isEven( int x ) {
    return ( x &amp; 1 ) == 0;
}

}