2

我将为初学者更好地解释标题。我的问题与常见问题非常相似：查找整数数组问题的所有排列。

我试图在给定整数列表和目标数字的情况下查找是否可以从列表中选择数字的任何组合，以便它们的总和与目标匹配。它必须使用函数式编程实践来完成，这意味着所有循环和突变都已经结束，只有巧妙的递归。完全公开：这是一个家庭作业，方法头由教授设置。这就是我所拥有的：

public static Integer sum(final List<Integer> values) {
     if(values.isEmpty() || values == null) {
             return 0;
     }
     else {
             return values.get(0) + sum(values.subList(1, values.size()));
     }
 }

public static boolean groupExists(final List<Integer> numbers, final int target) {
     if(numbers == null || numbers.isEmpty()) {
             return false;
     }
     if(numbers.contains(target)) {
             return true;
     }
      if(sum(numbers) == target) {
              return true;
      }
      else {
              groupExists(numbers.subList(1, numbers.size()), target);
              return false;
      }
  }

sum 方法已经过测试和工作，groupExists 方法是我正在研究的方法。我认为它非常接近，如果给定一个列表 [1,2,3,4]，它将对 3 和 10 等目标返回 true，但对 6 则返回 false，这让我感到困惑，因为 1,2,3 是正确的并添加到 6。显然缺少一些东西。此外，我正在查看的主要问题是它没有测试所有可能的组合，例如，第一个和最后一个数字没有被加在一起作为一种可能性。

更新：根据西蒙的回答工作了一段时间后，这就是我所看到的：

public static boolean groupExists(final List<Integer> numbers, final int target) {
     if(numbers == null || numbers.isEmpty()) {
             return false;
      }
     if(numbers.isEmpty()) {
              return false;
      }
      if(numbers.contains(target)) {
              return true;
      }
      if(sum(numbers.subList(1, numbers.size())) == (target - numbers.get(0))) {
              return true; }                                                                                                                                                                                                     
      else {
              return groupExists(numbers.subList(1, numbers.size()), target);
      }
  }
4

4 回答 4

1

假设您有n数字a[0], a[1], ..., a[n-1]，并且您想知道某个子集是否等于N。

假设你有这样一个子集。现在，要么a[0]包含，要么不包含。如果包含，则必须存在a[1], ... 的子集，a[n]其总和为N - a[0]。如果不是，则存在a[1], ... 的子集，a[n]总和为N。

这将引导您找到递归解决方案。

于 2012-12-01T22:37:29.443 回答
1

检查所有组合是次要的（您的实现有点遗漏）。为什么不尝试不同的（动态）方法：请参阅Hitchhikers Guide to Programming Contests，第 1 页（子集总和）。

您的主要方法将类似于：

boolean canSum(numbers, target) {
  return computeVector(numbers)[target]
}

computeVector返回包含所有数字的向量，这些数字可以与 的集合相加numbers。该方法computeVector以递归方式执行有点棘手，但您可以执行以下操作：

boolean[] computeVector(numbers, vector) {
  if numbers is empty:
    return vector

  addNumber(numbers[0], vector)

  return computeVector(tail(numbers), vector);
}

addNumber将采用向量并用新的“可行”数字“填充”（请参阅​​搭便车者以获取解释）。addNumber也可能有点棘手，我把它留给你。基本上你需要以递归方式编写以下循环：

for(j=M; j>=a[i]; j--)
  m[j] |= m[j-a[i]];
于 2012-12-01T22:23:55.943 回答
1

为方便起见，声明

static Integer head(final List<Integer> is) {
  return is == null || is.isEmpty()? null : is.get(0);
}
static List<Integer> tail(final List<Integer> is) {
  return is.size() < 2? null : is.subList(1, is.size());
}

那么你的功能是这样的：

static boolean groupExists(final List<Integer> is, final int target) {
  return target == 0 || target > 0 && head(is) != null &&
       (groupExists(tail(is), target) || groupExists(tail(is), target-head(is)));
}

毫无疑问，定期检查基本情况加上最后一行，其中左右操作数分别搜索包含或不包含头部的“组”。

我编写它的方式乍一看很明显，这些都是纯函数，但是，由于这是 Java 而不是 FP 语言，因此这种编写方式并不理想。最好将任何多次发生的函数调用缓存到最终的本地变量中。当然，这仍然是书本上的。

于 2012-12-02T07:25:31.693 回答
0

可以通过在每次递归时询问一个非常简单的决定来获得所有可能组合的列表。这个组合是否包含我列表的头部？要么有，要么没有，所以每个阶段有 2 条路径。如果任一路径导致解决方案，那么我们希望返回 true。

boolean combination(targetList, sourceList, target)
{
    if ( sourceList.isEmpty() ) {
        return sum(targetList) == target;
    } else {
        head = sourceList.pop();
        without = combination(targetList, sourceList, target); // without head
        targetList.push(head);
        with = combination(targetList, sourceList, target); // with head
        return with || without;
    }
}
于 2012-12-01T22:55:05.967 回答