arr动态规划的最短子集和

Question

我的目标是找到一个数组的和等于目标的最短子集。我尝试使用以下解决方案(动态规划):

public static List<Integer> bestSum_efficient(int targetSum, int[] numbers) {
return bestSum_efficient(targetSum, numbers, new HashMap<>());
}
public static List<Integer> bestSum_efficient(int targetSum, int[] numbers, Map<Integer, List<Integer>> map) {
if (map.containsKey(targetSum)) {
return map.get(targetSum);
}
if (targetSum == 0)
return new ArrayList<>();
if (targetSum < 0)
return null;
List<Integer> shortestCombination = null;
for (int n : numbers) {
List<Integer> remainedCombination = bestSum_efficient(targetSum - n, numbers,map);
if (remainedCombination != null) {
remainedCombination.add(n);
if (shortestCombination == null || shortestCombination.size() > remainedCombination .size()) {
shortestCombination = remainedCombination ;
}
}
}
map.put(targetSum, shortestCombination);
return shortestCombination;
}

用这段代码，我尝试运行以下测试:

System.out.println(bestSum_efficient(8, new int[]{1, 4, 5})); // [4,4]

我得到:[4,1,4]

当我将第一个if的内容更改为以下内容时，一切正常:

for (int n : numbers) {
List<Integer> remainedCombination = bestSum_efficient(targetSum - n, numbers,map);
if (remainedCombination != null) {
List<Integer> combination = new ArrayList<>();
combination.add(n);
combination.addAll(remainedCombination);
if (shortestCombination == null || shortestCombination.size() > combination.size()) {
shortestCombination = combination;
}
}
}

为什么在每次迭代中创建一个新的组合列表可以工作，而使用返回的剩余组合列表却不能?

Answer 1

经过一番思考，我想我找到了这个问题的根本原因。

在第一个场景中:

List<Integer> remainedCombination = bestSum_efficient(targetSum - n, numbers,map);
if (remainedCombination != null) {
remainedCombination.add(n);

我们直接修改列表remainedCombination，在其末尾加上n。当函数bestSum_efficient通过以下行返回保存的条目时，这实际上会修改我们用于记忆的HashMap条目:

if (map.containsKey(targetSum)) {
return map.get(targetSum);
}

在这种情况下，remainedCombination将是对map.get(targetSum)的引用，因此执行remainedCombination.add(n);相当于执行map.get(targetSum).add(n);

但是，如果在检查长度条件if (shortestCombination == null || shortestCombination.size() > remainedCombination .size()) {

之前，我们找到了到达目标和的最短方法，而不是直接在for循环中，那么我们只希望在bestSum_efficient

函数末尾修改HashMap的条目。在第二个(有效的)示例中，我们创建了一个新的临时ArrayList

List<Integer> combination = new ArrayList<>();
combination.add(n);
combination.addAll(remainedCombination);

，然后添加n。因此，这不会影响用于记忆的HashMap，它只会在函数的return之前被修改:

map.put(targetSum, shortestCombination);
return shortestCombination;