子集和变体

Question

我阅读了所有子集和主题，但在实现算法时仍然存在以下问题。

给定N个整数(N<=20)的数组A

• ai<=20
• values不必是唯一的

以及整数K (K<=20)。

规则

如果两个或多个数组数之和等于K，则用K. covered.

• Each
• “覆盖”等于K的
  • 数组项，这些数字也是数组中的
  • 数，只能覆盖一次。

示例

N=6，整数: 1，1，2，3，4，5

K=4

可能覆盖范围

介绍了

1. coverage
   • 4。1+1+2=4.

覆盖

• 1、1、2。

​

1+3=4.覆盖

2. • 4，
   • 1、3被覆盖。

​

K=5

可能覆盖范围

covered.

• 1,1,3

1. coverage
   • 5是作为1+1+3=5.

覆盖的

​

2+3=5.覆盖

1. coverage
   • 5，
   • 1，4覆盖1+4=5，
   • 2，3被覆盖

​

目标：

对于给定的数组A和整数K，查找所有可能的“覆盖”。我需要所有的覆盖范围，而不仅仅是覆盖大部分数组项的覆盖范围。

我尝试了两种方法--

1. Brut力算法.检查所有可能大小的子集是有效的，但是即使只检查10个数字也要花费太多的时间。我需要它以500ms.
2. First，的形式完成，我按降序对数组进行排序。然后，对于每一个可能的子和数，我创建“插槽”。我循环遍历数组，并在插槽中按如下规则放置数字:如果插槽的和等于K，则在插槽中放置数字。在插槽中有最小和的slots.

• 放置数字。

• 在插槽中放置数字，给出所有的

• 的密室和K。

​

嗯，第二种方法很有效，而且效果很快。但是我发现了一些没有覆盖的场景。

如果有人能提出解决这个问题的主意，我将不胜感激。

我希望我能很好地解释这个问题。

谢谢。

Answer 1

我没有现成的答案，但我建议你看看“装箱问题”--在这里可能有用。

主要的问题是找出所有可能的数字K，所以试试这个：

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

我在这里用上面的数字在K=8上运行它，在这里，我们在两个不同的地方重用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);
    }
}