Subset Problem.

상수 X가 있고, 배열 A가 있다는 가정하에 A의 배열을 X에 가까운 합의 배열로 재 정렬하라 라는 문제인데.

찾아보니 가방문제와 비슷 하다는 겁니다. 이를 서브셋 프러블럼이라고 하는데...

예를 들면, X = 200 , A = { 19, 151, 34, 32, 132, 99, 43 } 이다 하면

151, 43, 132, 34, 32, 99, 19로 재 배열되는 원리죠... 자바로 한번 짜보면 아래의 함수와 같습니다.

public static String sortArray(int a[], int K)
    {
     
        List<Integer> inputs = Arrays.asList(ArrayUtils.toObject(a)); //Arrays.asList(19,23,41,5,40,36);
        
        SubList opt = new SubList();
        Set<SubList> sums = new HashSet<>();
        sums.add(opt);  
  
        for (Integer input : inputs) {
            Set<SubList> newSums = new HashSet<>();                      
            for (SubList sum : sums) {
            List<Integer> newSubList = new ArrayList<>(sum.subList);
            newSubList.add(input);
            SubList newSum = new SubList(sum.size + input, newSubList);        
 
            if (newSum.size <= K) {
                newSums.add(newSum);
                update optimum                       
                if (newSum.size > opt.size) {
                    opt = newSum;
                }
            }
        }
        
        sums.addAll(newSums);
  }
    if (opt.subList.toString() != "[]") System.out.println(opt.subList.toString());
 
    return opt.subList.toString();
}
 
 

위 함수를 반복하여 돌리는 데, 찾은 값들은 A배열에서 제거 후, A배열의 남아있는 값이 없을때 까지 반복문을 돌리시면 됩니다.