达到目标整数 - java

我有一个随机长度的数组，里面充满了随机整数。为了简单起见，它们从最高到最低排序。

我也有一个目标随机整数。

我需要获取所有总和大于或等于目标的组合，而无需使用不必要的数字。给出以下示例:

nums = [10, 6, 5, 3, 2, 1, 1]

target = 8

我想要这个输出:

10 (10 is higher or equal to 8, so there's no need to sum it)

6+5

6+3

6+2

6+1+1

5+3

5+2+1

5+2+1 (Note that this result is different from the previous since there are 2 1s)

我尝试了很多递归策略，但找不到正确的答案。不需要特定的语言，欢迎使用伪代码。

编辑:邮编

private static boolean filtrar(final CopyOnWriteArrayList<Padre> padres) {
        if (sum(padres) < TARGET) {
            return false;
        }
        int i;
        for (i = padres.size(); i >= 0; i--) {
            if (!filtrar(copiaPadresSinElemento(padres, i-1))) {
                break;
            }
        }
        // Solución óptima, no se puede quitar nada.
        if (i == padres.size()) {
            print(padres);
        }
        return true;
    }

    private static int sum(final CopyOnWriteArrayList<Padre> padres) {
        int i = 0;
        for (final Padre padre : padres) {
            i += padre.plazas;
        }
        return i;
    }

    private static void print(final CopyOnWriteArrayList<Padre> padres) {
        final StringBuilder sb = new StringBuilder();
        for (final Padre padre : padres) {
            sb.append(padre);
            sb.append(", ");
        }
        final String str = sb.toString();
        System.out.println(str);
    }

    private static CopyOnWriteArrayList<Padre> copiaPadresSinElemento(
            final CopyOnWriteArrayList<Padre> padres, final int i) {
        final CopyOnWriteArrayList<Padre> copia = new CopyOnWriteArrayList<Padre>();
        for (int e = 0; e < padres.size(); e++) {
            if (e != i) {
                copia.add(padres.get(e));
            }
        }
        return copia;
    }

Padre是一个简单的对象，其中包含每个数字的名称。 Padre.plazas是数字。

现在的数组是[6,4,4,4,3,3,3]，目标是8。

参考方案

我认为这样会起作用:

function filter(array, target): Boolean{ //assumes array is sorted in descending order
  if(sum(array) < target) return false;
  for(i = array.length-1; i>=0; --i){
    if(! filter(array.createCopyRemovingElementAt(i), target)) break;
  }
  if(i==array.length-1) print(array); // solution is "optimal": could not remove a single number
  return true;
}

Java:正则表达式模式匹配器是否有大小限制？ - java

我的模式类似于OR:“word1 | word2 | word3”我大约有800个字。可能有问题吗？参考方案您仅受记忆和理智的限制。 :)

Java:线程池如何将线程映射到可运行对象 - java

试图绕过Java并发问题，并且很难理解线程池，线程以及它们正在执行的可运行“任务”之间的关系。如果我创建一个有10个线程的线程池，那么我是否必须将相同的任务传递给池中的每个线程，或者池化的线程实际上只是与任务无关的“工人无人机”可用于执行任何任务？无论哪种方式，Executor / ExecutorService如何将正确的任务分配给正确的线程？参考方案 …

JAVA:字节码和二进制有什么区别？ - java

java字节代码（已编译的语言，也称为目标代码）与机器代码（当前计算机的本机代码）之间有什么区别？我读过一些书，他们将字节码称为二进制指令，但我不知道为什么。参考方案字节码是独立于平台的，在Windows中运行的编译器编译的字节码仍将在linux / unix / mac中运行。机器代码是特定于平台的，如果在Windows x86中编译，则它将仅在Win…

java:继承 - java

有哪些替代继承的方法？ java大神给出的解决方案有效的Java：偏重于继承而不是继承。（这实际上也来自“四人帮”）。他提出的理由是，如果扩展类未明确设计为继承，则继承会引起很多不正常的副作用。例如，对super.someMethod()的任何调用都可以引导您通过未知代码的意外路径。取而代之的是，持有对本来应该扩展的类的引用，然后委托给它。这是与Eric…

Java:BigInteger，如何通过OutputStream编写它 - java

我想将BigInteger写入文件。做这个的最好方式是什么。当然，我想从输入流中读取（使用程序，而不是人工）。我必须使用ObjectOutputStream还是有更好的方法？目的是使用尽可能少的字节。谢谢马丁参考方案 Java序列化（ObjectOutputStream / ObjectInputStream）是将对象序列化为八位字节序列的一种通用方法。但…

达到目标整数 - java

腾讯的同事天天给我安利让我看《三体》，说马化腾和雷军也在…