明白人的gravatar头像
明白人 2015-03-06 09:50:09

如何通过java实现通用组合算法?

例子 用5升汽油,商店有1升、2升、3升,求有多少组合?写个通用算法(前面数值只是例子可能要用6升,商店不一定只有这几个升数)

2个3升 5个1升  3个2升也行 

所有回答列表(5)
剑八的gravatar头像
剑八  LV2 2015年3月6日

 

public class PetrolRecursion {
    int target = 10;//要得到的总数
    int[] sources = new int[]{1,2,3};//原始数据,默认从小到大已经排好序了
    int arr_length = sources.length;//数组长度
    @Test
    public void test(){
        int m = target/sources[0];
        Set<List<Integer>> set = new HashSet<List<Integer>>();
        for(int i=1;i<=m;i++){ //i从1循环到5,组合1个数字到5个数字的5种情况
            int[] indexs = new int[i];
            recursion(indexs,0,i,set);
        }
        System.out.println("组合出"+target+"的情况,去重后的结果是");
        for(List<Integer> l:set){
            for(int i:l){
                System.out.print(i + " ");
            }
            System.out.println();
        }
    }

    //递归函数
    public boolean recursion(int[] indexs,int depth,int m,Set<List<Integer>> set){
        if(depth==m){
            List<Integer> list = new ArrayList<Integer>();
            for(int i=0;i<m;i++){
                list.add(sources[indexs[i]]);
            }
            int sum = filter(list);
            if(sum==target) {
                Collections.sort(list);//去重,如果不要去重可以注释掉这一行
                set.add(list);
            }
            if(sum>=target){
                return true;//已经找到,不需要继续循环
            }
            return false;
        }else{
            for(int k=0;k<arr_length;k++){
                indexs[depth] = k;
                boolean b = recursion(indexs,depth+1,m,set);
                if(b){
                    break;
                }
            }
            return false;
        }
    }

    //过滤
    public int filter(List<Integer> arr){
        int sum = 0;
        for(int i:arr){
            sum+=i;
        }
        return sum;

    }
}

 

如何通过java实现通用组合算法?

如何通过java实现通用组合算法?

如何通过java实现通用组合算法?

  • -------------------------------

有同学说超买可以符合要求,这样的话将filter方法里的return语句改一下就可以了

 

如何通过java实现通用组合算法?如何通过java实现通用组合算法?

评论(9) 最佳答案
eviling的gravatar头像
eviling  LV7 2015年3月6日

我就是过来凑个热闹smiley

kiky的gravatar头像
kiky  LV10 2015年3月6日

描述的感觉有点问题。

响尾蛇的gravatar头像
响尾蛇  LV15 2015年3月6日

脑子比较笨,想不出什么好办法!

public class Test {
	public static void main(String[] args) {
		//1,2,3
		//5
		System.out.println(doSome(5));
	}
	public static int doSome(int total){
		int count = 0;
		for(int i=0;i<=total/1;i++){//1
			for(int j=0;j<=total/2;j++){//2
				for(int k=0;k<=total/3;k++){//3
					if((i+2*j+3*k)==5){
						System.out.println(i+" ,"+j+" ,"+k);
						count++;
					}
				}
			}
		}
		return count;
	}
}

 

public class Test4 {
	public static int count = 0;
	public static void main(String[] args) {
		int total = 5;
		int[] types = {1,2,3};
		
		List<Integer> list = new ArrayList<Integer>();
		int beginIndex = 0;
		int result = 0;
		
		doRecursion(types,beginIndex,total,result,list);
		System.out.println(count);
	}
	
	public static void doRecursion(int[] types,int beginIndex,int total,int result,List<Integer> list){
		if(result>=total){
			if(result==total){
				System.out.println(list);
				count++;
			}
			return;
		}
		for(int i=beginIndex;i<types.length;i++){
			list.add(i);
			doRecursion(types,i,total,result+types[i],list);
			list.remove(Integer.valueOf(i));
		}
	}
}

 

明白人的gravatar头像
明白人  LV6 2015年3月6日

效率差点数字大了直接死机了

 

顶部 客服 微信二维码 底部
>扫描二维码关注最代码为好友扫描二维码关注最代码为好友