Subset Problem 2

Subset sum Problem이란, A라는 배열내의 원소들의 합이 K에 가까운 수를 나열하는 것인데. 가령 예를 들자면

A = { 1, 2, 3, 4, 5, 6, 7, 8 } 이 있고 K가 9 일때

[1,8] , [2, 7], [3, 6], [4, 5] 로 나열되는게 가장 이상적이다.

그렇다고해서 가장 큰수를 가지고 노는것도 이상하다.

자료를 찾아봤는데 위키디피아에는 이렇게 정의되어 있다.

출처 https://en.wikipedia.org/wiki/Subset_sum_problem에 의하면.

An approximate version of the subset sum would be: 변수는 N x1, x2, ..., xN 그리고 합 s, 결과 output이 주어져야 한다.

yes, 부분 집합들의 합들이 s에 가까워지면;

no, 부분 집합들의 합들이 (1 − c)s 와 s 보다 작은 c > 0 조건이면;

any answer, 또한 (1 − c)s 와 s  s에 가장가까운 합이 없으면.

If all numbers are non-negative, the approximate subset sum is solvable in time polynomial in N and 1/c.

The solution for subset sum also provides the solution for the original subset sum problem in the case where the numbers are small (again, for nonnegative numbers). If any sum of the numbers can be specified with at most P bits, then solving the problem approximately with c = 2−P is equivalent to solving it exactly. Then, the polynomial time algorithm for approximate subset sum becomes an exact algorithm with running time polynomial in N and 2P (i.e., exponential in P).

인데,

결과만 보자면 이러하다 아래는 슈도 코드이다.

 
initialize a list S to contain one element 0.
for each i from 1 to N do
  let T be a list consisting of xi + y, for all y in S
  let U be the union of T and S
  sort U
  make S empty 
  let y be the smallest element of U 
  add y to S 
  for each element z of U in increasing order do
     //trim the list by eliminating numbers close to one another
     //and throw out elements greater than s
    if y + cs/N < z ≤ s, set y = z and add z to S 
if S contains a number between (1 − c)s and s, output yes, otherwise no

이렇게 해도, i는 처음부터 시작하기 때문에 맨 위에 예제에서 [1,2,3] 이 제일먼저 나올 터인데. 결과값이야 얼추 나오긴 나오지만. 이상적은 아니다.

그래서 이상적인 코드는 어떻게 짜야 할까? 뭐. 나름 난제다. 다음 조건에만 부합하면 된다.

1. 배열중 가장 큰 값을 선택하고 while(K보다 작고 같지 않아야한다)

2. 다음 선택되는 수와 더해보고 K보다 작은지 검사한다.

   여기서 다음 선택되는 수는 따로 함수를 돌려 Closest가 아닌 Equal이 되는 수를 찾아봄이 좋다.

   이는 isZero 함수에서 0을 k로 바꿔주면 해결된다.

3. 다음 선택되는 수로도 없다면, 배열중 가장 작은 값을 선택하고, 다음 선택 되는 수를 찾아본다.

   이를 설계하려면 n pair subsets sum to K라는 keyword로 article을 찾아보는게 좋다.

   즉, 간단히 말하자면 가장 큰 값 + 가장 작은 값 + n...... 중 k에 equal하는 수를 찾아 보는것이다.

   흐름은 Max + Min + n = equal 혹은 Max + Min + n1 + n2 = equal 식으로 흘러가야 하는 것.

   for을 2차원 내에서 꼭 끝내야 하고, 호출하는 함수에서 또 나누어 주어도 좋다.

4. 위 조건들에 부합하는 나열이 나오면, 그 나열이 있는수를 따로 뺀 새로운 arr를 만들어 준다.

   가령 1,2,3,4,5,6,7,8 이고 K가 9일때, 1,8이 조건에 부합하니 1,8은 arr에서 빼주어야 한다. 0으로 만들어주고

   조건을 검사하는 함수에서 원소가 0이 아닐때로 셋팅해주어도 좋다.

5. 위 과정을 반복한다

인데, 차례차례 시간두어 만들어 봐야겠다.!

일단 1차적으로 Subset을 i =0부터 돌리면 아래의 함수와 같다.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
 
import org.apache.commons.lang3.ArrayUtils;
 
public class SubList {
 
    public int size;
    public List<Integer> subList;
 
    public SubList() {
        this(0, new ArrayList<>());
    }
 
    public SubList(int size, List<Integer> subList) {
        this.size = size;
        this.subList = subList;
    }
 
    public static SubList extraArray(int arr[], int k) {
        List<Integer> inputs = Arrays.asList(ArrayUtils.toObject(arr));
        SubList opt = new SubList();
 
        Set<SubList> sums = new HashSet<>();
        sums.add(opt);
 
        for (Integer input : inputs) {
            Set<SubList> newSums = new HashSet<>();
 
            for (SubList sum1 : sums) {
                List<Integer> newSubList = new ArrayList<>(sum1.subList);
                newSubList.add(input);
                SubList newSum = new SubList(sum1.size + input, newSubList);
 
                if (newSum.size <= k) {
                    newSums.add(newSum);
 
                    if (newSum.size > opt.size) {
                        opt = newSum;
                    }
                }
            }
 
            sums.addAll(newSums);
        }
 
        return opt;
    }
 
    public static int[] loopArray(int[] src, SubList del) {
        ArrayList<Integer> rst = new ArrayList<Integer>();
        int[] rsts;
 
        for (int i = 0; i < src.length; i++) {
            for (int j = 0; j < del.subList.size(); j++) {
                if (src[i] == del.subList.get(j)) {
                    src[i] = 0;
                }
            }
        }
 
        for (int i = 0; i < src.length; i++)
            if (src[i] != 0)
                rst.add(src[i]);
 
        rsts = new int[rst.size()];
 
        for (int i = 0; i < rsts.length; i++)
            rsts[i] = rst.get(i);
 
        return rsts;
 
    }
 
    public static boolean isAllZero(int[] arr) {
        for (int i = 0; i < arr.length; i++)
            if (arr[i] != 0)
                return true;
        return false;
    }
 
    public static void main(String args[]) {
        int arr[] = { 6, 31, 22, 34, 11, 25, 25, 34, 17, 23, 14, 19 };
        int k = 44;
 
        while (true) {
            if (isAllZero(arr) == false)
                break;
 
            SubList result = extraArray(arr, k);
            System.out.println(result.subList.toString());
            arr = loopArray(arr, result);
        }
    }
}

결과:[25, 19][6, 23, 14][31, 11][22, 17][34]

Subset Problem 1과 같은 구성으로 만들자면 아래와 같다.

import java.util.*;
 
public class SubList {
 
    public static void main(String args[]) {
        int arr[] = { 1, 3, 4, 8, 10 };
        int k = 15;
 
        ArrayList<Integer> temp = new ArrayList<Integer>();
        for (int i = 0; i < arr.length; i++)
            temp.add(arr[i]);
 
        while (true) {
            if (temp.size() <= 1)
                break;
 
            Collections.sort(temp);
 
            ArrayList<Integer> set = new ArrayList<Integer>();
 
            set.add(temp.get(temp.size() - 1));
            temp.remove(temp.size() - 1);
 
            for (int i = temp.size() - 1; i >= 0; i--) {
                if (temp.get(i) + allSum(set) <= k) {
                    set.add(temp.get(i));
                    temp.remove(i);
                }
            }
 
            printResult(set);
        }
 
    }
 
    public static void printResult(ArrayList<Integer> set) {
        for (int i = 0; i < set.size(); i++) {
            if (i == 0)
                System.out.print("[" + set.get(i) + ", ");
            else if (i == set.size() - 1)
                System.out.print(set.get(i) + "]" + System.lineSeparator());
            else
                System.out.print(set.get(i) + ", ");
        }
    }
 
    public static int allSum(ArrayList<Integer> set) {
        int rs = 0;
        for (int i = 0; i < set.size(); i++)
            rs += set.get(i);
 
        return rs;
    }
}