하위 집합 합계의 변형

Question

모든 하위 집합 합계 주제를 읽었지만 다음 문제에 대한 알고리즘을 구현하는 데 여전히 문제가 있습니다. N 정수의 배열 소정

(N < = 20) 여기서

• 값

및 정수 고유하지 않아도 < = 20

A [i]를 K (K < = 20). 규칙

는 : K 동일

• 배열 항목은 둘 개 또는 그 이상의 배열 번호 합 K 같으면 이러한 수치도 포함된다
• K.에 "적용"된다.
• 배열의 각 번호는 한 번만 적용 할 수 있습니다.

예 :

N = 6, 정수 1, 1, 2, 3, 4, 5

K = 4

가능한 커버리지 :

1. 적용 범위
   • 4가 포함됩니다.
   • 1, 1, 2는 1 + 1 + 2 = 4로 포함됩니다.
2. 따르면
   • 4 덮여있다.
   • 1, 3은 1 + 3 = 4로 커버됩니다.

K = 5

가능한 커버리지 :

1. 따르면
   • 5 덮여있다.
   • 1,1,3은 1 + 1 + 3 = 5로 포함됩니다.
2. 따르면
   • 5 덮여있다.
   • 1,4는 1 + 4 = 5로 덮여 있습니다.
   • 2,3은 2 + 3 = 5로 포함됩니다.

목표 :

지정된 배열 A와 정수 K의 경우, 모든 가능한 "적용 범위"를 찾을 수 있습니다. 대부분의 배열 항목을 다루는 것뿐만 아니라 모든 커버리지가 필요합니다.

1. 단맛 힘 알고리즘 :

   나는 두 가지 방법으로 노력했다. 가능한 모든 가능한 모든 하위 세트를 검사하지만 10 개의 숫자만으로 너무 많은 시간이 걸립니다. 나는 500ms 이내로 끝내야한다.

2. 먼저 배열을 내림차순으로 정렬했습니다. 그런 다음 가능한 각 하위 합계 수에 대해 "슬롯"을 만듭니다. 같은 규칙에 따라 슬롯에 I 배열을 반복 넣고 번호 : 슬롯에
   • 넣어 수의 합이 전체 슬롯의 최소 합을 갖는 슬롯
   • 넣어 수 K. 동일하게하는 경우.
   • 모든 슬롯의 K에 클로짓 총계를 제공하는 슬롯에 번호를 넣습니다.

글쎄, 두 번째 방법은 작동하고 빠르게 작동합니다. 그러나 일부 보상 범위가없는 시나리오를 발견했습니다.

누군가이 문제를 해결하기위한 아이디어를 제공하면 감사하겠습니다.

나는이 문제를 잘 설명하기를 바랍니다.

감사합니다.

Answer 1

나는 그것에 대한 대답이 없지만 여기 '유용 포장 문제'를 살펴 보는 것이 좋습니다.

Collection All_Possible_Sums_GivingK; 

find_All_Sums_Equal_To_K(Integer K, Array A) 
{ 
    /* this function after finding result 
    add it to global Collection AllPossibleSumsGivingK; */ 
    find_All_Elements_Equal_To_K(Integer K, Array A); 

    Array B = Remove_Elements_Geater_Or_Equal_To_K(Integer K, Array A); 

    for all a in A { 
     find_All_Sums_Equal_To_K(Integer K-a, Array B-a) 
    } 
} 

Answer 2

내가 다른 부분 집합 합 변형에게 준 이전의 대답에서이 수정 : https://stackoverflow.com/a/10612601/120169

I

가장 큰 문제는 수 K. 그래서 이것을 시도주는 모든 가능한 금액을 찾을 수 있습니다 위의 숫자와 함께 K = 8의 경우 여기에서 실행합니다. 여기서 두 개의 "커버리지"중 하나에 대해 2 개의 다른 장소에서 1을 재사용합니다. 그것이 당신을 위해 어떻게 작동하는지 알려주십시오.

public class TurboAdder2 { 
    // Problem inputs 
    // The unique values 
    private static final int[] data = new int[] { 1, 2, 3, 4, 5 }; 
    // counts[i] = the number of copies of i 
    private static final int[] counts = new int[] { 2, 1, 1, 1, 1 }; 
    // The sum we want to achieve 
    private static int target = 8; 

    private static class Node { 
     public final int index; 
     public final int count; 
     public final Node prevInList; 
     public final int prevSum; 
     public Node(int index, int count, Node prevInList, int prevSum) { 
      this.index = index; 
      this.count = count; 
      this.prevInList = prevInList; 
      this.prevSum = prevSum; 
     } 
    } 

    private static Node sums[] = new Node[target+1]; 

    // Only for use by printString and isSolvable. 
    private static int forbiddenValues[] = new int[data.length]; 

    private static boolean isSolvable(Node n) { 
     if (n == null) { 
      return true; 
     } else { 
      while (n != null) { 
       int idx = n.index; 
       // We prevent recursion on a value already seen. 
       // Don't use any indexes smaller than lastIdx 
       if (forbiddenValues[idx] + n.count <= counts[idx]) { 
        // Verify that none of the bigger indexes are set 
        forbiddenValues[idx] += n.count; 
        boolean ret = isSolvable(sums[n.prevSum]); 
        forbiddenValues[idx] -= n.count; 
        if (ret) { 
         return true; 
        } 
       } 
       n = n.prevInList; 
      } 
      return false; 
     } 
    } 

    public static void printString(String prev, Node n, int firstIdx, int lastIdx) { 
     if (n == null) { 
      printString(prev +" |", sums[target], -1, firstIdx); 
     } else { 
      if (firstIdx == -1 && !isSolvable(sums[target])) { 
       int lidx = prev.lastIndexOf("|"); 
       if (lidx != -1) { 
        System.out.println(prev.substring(0, lidx)); 
       } 
      } 
      else { 
       while (n != null) { 
        int idx = n.index; 
        // We prevent recursion on a value already seen. 
        // Don't use any indexes larger than lastIdx 
        if (forbiddenValues[idx] + n.count <= counts[idx] && (lastIdx < 0 || idx < lastIdx)) { 
         // Verify that none of the bigger indexes are set 
         forbiddenValues[idx] += n.count; 
         printString((prev == null ? "" : (prev + (prev.charAt(prev.length()-1) == '|' ? " " : " + ")))+data[idx]+"*"+n.count, sums[n.prevSum], (firstIdx == -1 ? idx : firstIdx), idx); 
         forbiddenValues[idx] -= n.count; 
        } 
        n = n.prevInList; 
       } 
      } 
     } 
    } 

    public static void main(String[] args) { 
     for (int i = 0; i < data.length; i++) { 
      int value = data[i]; 
      for (int count = 1, sum = value; count <= counts[i] && sum <= target; count++, sum += value) { 
       for (int newsum = sum+1; newsum <= target; newsum++) { 
        if (sums[newsum - sum] != null) { 
         sums[newsum] = new Node(i, count, sums[newsum], newsum - sum); 
        } 
       } 
      } 
      for (int count = 1, sum = value; count <= counts[i] && sum <= target; count++, sum += value) { 
       sums[sum] = new Node(i, count, sums[sum], 0); 
      } 
     } 
     printString(null, sums[target], -1, -1); 
    } 
}