某实习生招聘

3/8/2017来源:ASP.NET技巧人气:3402

看到题目,很显然是0,1背包问题,苦于平时练手不多,在正在开始写的时候犯难了,调试不通过,导致在规定的时间没提交,后悔不已。之后自己解决了代码问题,做个记录。

题目:给定数组{1,3,4,5,9,11,2},输出和为n的组合个数

分析:常规题目一般我给定连续的数组,如{1,2,3,4,5...,k},输出何为n的组合个数,而题目给定的数组非连续,因此在递归代码中势必需要有个中间flag用来记录选取信息。

直接贴自己写的java代码(没提交好遗憾)

import java.util.HashMap;
import java.util.Scanner;


public class Sum {
	static int length;
	static int[] value = {1,3,4,5,9,11,2};
	static HashMap<Integer,Integer> flag = new HashMap<Integer,Integer>();
	
	static int count = 0;
    static void findCombination(int sum,int index){
        if (index<0||sum<0) {
            return;
        }
        if (value[index]==sum) {
            flag.put(value[index], 1);
            for(Integer key:flag.keySet())
            	if(flag.get(key)==1){
            		System.out.PRint(key+" ");
            		
            	}
            flag.put(value[index],0);
            count++;
            System.out.println();
        }
        flag.put(value[index], 1);
        findCombination(sum-value[index],index-1);
        flag.put(value[index], 0);
        findCombination(sum,index-1);
    }
    public static void main(String[] args) {
        /*int n,m;
        Scanner s=new Scanner(System.in);
        n=s.nextInt();*/
        int n=4;
        flag.put(1, 0);
        flag.put(3, 0);
        flag.put(4, 0);
        flag.put(5, 0);
        flag.put(9, 0);
        flag.put(11, 0);
        flag.put(2, 0);
        findCombination(n,6);
        System.out.println(count);
    }

}