n选m 组合 算法的next函数(非递归方法)

/*
 *@auther 皇阿玛
 *2019.9.16
 */
package courseOne;

import java.util.Arrays;


class Combination implements ppppp{
	
	int total;//总人数
	private int[] people;//当前所选的人
	public Combination() {}
	public Combination(int total,int selectPeople) {
		this.people=new int[selectPeople];
		this.total=total;
		Integer a = 2;
	}
	
	
	public int[] nextTwo() {
		//判断数组是否为空
		int max=total-1;
		int flag=0;
		for(int i=0;i<people.length;i++) {
			flag+=people[i];
		}
		if(flag==0) {
			//初始化数组
			for(int i=0;i<people.length;i++) {
				people[i]=i;
			}
		}else {
			
			for(int i=people.length-1;i>=0;i--) {
				if(people[i]<max) {
					people[i]=people[i]+1;
					
					//当该位置的数据进行到判断前一位置时
					if(i<people.length-1) {
						/**
						 * version:3.0
						 * answer:right
						 * @author MrGao
						 */
						for(int j=i+1;j<people.length;j++) {
							//从前往后遍历数组,在之前数据的基础上加一
							int temp = people[j-1]+1;
							//如果当前修改数据超出预定数据,跳出
							if(temp==total-1) {
								break;
							}
							//将修改后的数据修改到源数据
							people[j]=temp;
						}
					}
					break;
				}else {
					max = max-1;
				}
			}
		}
		return people;
	}
	public int arrangement(int[][] array) {

		int len = people.length;
		
		int weight = 0;//求取某一个组合的权值之和
		for(int i = 0;i < len;i++)	//写一个双重for循环,因为是二维数组
		{
			for(int j = 0;j < len;j++)
			{
				weight += array[ people[i] ][ people[j] ];
			}
		}
		
//		Combination comb = new Combination(5,3);
		
		
		return weight;
	}
	
}

public class CombinationExample {

	public static void main(String[] args) {
		int[][] test=new int[][] {
								  {10,5,1,4,6},
								  {0,11,9,8,4},
								  {5,3,9,9,7},
								  {4,4,5,12,6},
								  {3,1,7,6,10}
								  };
	//输出数组

	Combination comb = new Combination(5,3);
	
	int sum=10;
	int TotalWeight = 0; //计算最终的最大的权值之和
	int[] zuhe={};
	while(sum>0) {
		int[] a =comb.nextTwo(); //求取下一个组合,以数组的形式保存
		int tem = comb.arrangement(test);

		//CombinationExample combEx = new CombinationExample();
		//int tem = combEx.arrangement(test, a);
		sum--;
		
		//当前组合已经存在a[i]中了,含有的元素个数为 selectPeople 个
//		TotalWeight =(TotalWeight>tem)? TotalWeight:tem ; 
		if(TotalWeight < tem)
		{
			TotalWeight = tem;
			zuhe = a;
		}
		
		
	}
	System.out.println(TotalWeight+" "+Arrays.toString(zuhe));
	}
	
//	private int weight = 0;//求取的组合之权值和
	
	public int arrangement(int[][] array,int[] people) {

		
		int len = people.length;
		
		int weight = 0;//求取某一个组合的权值之和
		for(int i = 0;i < len;i++)	//写一个双重for循环,因为是二维数组
		{
			for(int j = 0;j < len;j++)
			{
				weight += array[ people[i] ][ people[j] ];
			}
		}
		
		
		return weight;
	}

}

 

上一篇:css隐藏滚动条


下一篇:【模板】模拟退火 费马点以及最小球覆盖