我想找到与给定目标相加的最小子阵列。 我的输入是输入数组和目标总和。
我知道这个问题已被多次询问，但在大多数情况下，人们正试图找到所有可能的组合，这些组合可以增加他们的目标，或者他们的解决方案不允许重复。
在我的例子中，我想只找到最小的子数组，并允许从输入数组中复制数据。
例如，给定[1,4,10,20,35]的输入数组和17的目标，我期望[10,4,1,1,1]的输出数组。
因此，允许我的算法在查找输出时复制输入数组中的任何值。
这是我到目前为止所拥有的：
public static ArrayList<Integer> representNumberAsSumOfArrayElements(ArrayList<Integer> inputs, int target)
{
ArrayList<Integer> result = new ArrayList<>();
//First sort the input array in descending order
Collections.sort(inputs, Collections.reverseOrder());
int i = 0;
//Iterate through the input array and break down the target into a sum of the input array
while (i < inputs.size() && target > 0) {
if(target >= inputs.get(i) ) {
result.add(inputs.get(i));
target = target - inputs.get(i);
} else {
i++;
}
}
return result;
}
只是一个简单的驱动程序来测试100个目标上的代码：
public static void main(String[] args) {
ArrayList<Integer> inputs = new ArrayList<>(Arrays.asList( 1, 4, 10, 20, 35, 56, 84));
int n = 100;
ArrayList<Integer> sumArray = new ArrayList<>();
for (int i = 0; i <= n; i++)
{
sumArray = representNumberAsSumOfArrayElements(inputs, i); // O(n)
System.out.println(i + " written as a sum of array elements " + sumArray);
}
}
我已经实现了一个适用于大多数值的O(n)算法，但在某些情况下，我得到了错误的结果。
例如，当我使用[1,4,10,20,35,56,84]的输入和69的目标和运行我的代码时，正确的输出将是[35,20,10,4]但我的算法输出[56,10,1,1,1]。
我理解为什么我的算法错了，但我不知道如何解决它。
首先创建一个前缀和数组，使prefSum [i]给出从索引0到i（包括两者）的给定数组的所有元素的总和。如果你的数组包含所有正整数，则prefSum数组被排序，你可以进行二进制搜索。因此，将prefSum数组从0扫描到长度并在0到（i-1）之间进行二进制搜索，如果当前索引是i并尝试找到最大j，其中j在0到i-1之间，这样prefSum [i] -prefSum [j] =给定目标。总体复杂性将是nlogn。
术语subarray通常假设连续的数组（这就是为什么一些分析者意味着另一个问题），但是你的排序告诉我们情况并非如此，你需要任意顺序的最小项目列表来解决重复的子集和问题。
您可以使用表格方法解决当前使用动态编程的问题（而您的代码利用贪婪方法 - 在一般情况下不适用）。要获得最小的子集，您只需选择具有较短值列表的子问题解决方案。
看起来这个Python代码工作正常（未经过充分测试）。
def best(lst, summ):
lst = sorted(lst, reverse = True)
a = [[] for _ in range(summ + 1)] # list of lists
a[0].append(-1) # fake value to provide valid zero entry
for l in lst:
for i in range(summ + 1 - l):
t = len(a[i])
if t:
if (len(a[i + l]) == 0) or (t < len(a[i + l])):
a[i + l] = a[i] +[l] # concatenate lists
return a[summ][1:] #remove fake -1
for s in range(55, 71):
print(s, best([1,4,10,20,35,56,84], s))
55 [35, 20]
56 [56]
57 [56, 1]
58 [56, 1, 1]
59 [35, 20, 4]
60 [56, 4]
61 [56, 4, 1]
62 [56, 4, 1, 1]
63 [35, 20, 4, 4]
64 [56, 4, 4]
65 [35, 20, 10]
66 [56, 10]
67 [56, 10, 1]
68 [56, 10, 1, 1]
69 [35, 20, 10, 4]
70 [35, 35]
请注意，我们不需要自己存储列表 - 我将它们添加到调试和简单中。我们只需要存储给定总和中的最后一个附加值和项目数。 解除清单的解决方案：
def best1(lst, summ):
a = [(0,0)] * (summ + 1) # list contains tuples (value, bestcount)
a[0] = (-1,1)
for l in lst:
for i in range(summ + 1 - l):
t = a[i][1]
if t:
if (a[i + l][1] == 0) or (t < a[i + l][1]):
a[i + l] = (l, t + 1)
res = []
t = summ
while a[t][1] > 1:
res.append(a[t][0])
t = t - a[t][0]
return res
广度优先（BFS）方法的复杂性是O（n*k），其中n是数组中唯一元素的数量，k是最短答案的长度。伪代码如下：
1. remove duplicates from the input array, A:
can be done by copying it into a set in O(|A|)
2. build a queue of lists Q;
store the sum of elements as its 0th element,
and add an initially-empty list with a sum of 0
3. while Q is not empty,
extract the first list of Q, L
for each element e in A,
if L[0] + e == sum,
you have found your answer: the elements of L with e
if L[0] + e < sum,
insert a new list (L[0] + e, elements of L, e) at the end of Q
4. if you reach this point, there is no way to add up to the sum with elements of A
不使用列表的第0个元素作为总和会产生重新计算其元素总和的成本。在这个意义上，存储总和是动态编程的一种形式（=重用先前的答案以避免重新计算它们）。
这保证了加到sum的第一个列表也具有尽可能短的长度（因为队列中的所有列表都按长度的升序进行评估）。您可以通过添加启发式来选择首先评估哪个相同长度的列表来改善运行时（例如，最接近总和的那个）;但是，这只适用于特定输入，最坏情况的复杂性将保持不变。
由于您使用的是Java，我将使用动态编程（在本例中为递归）在Java中添加实现。
sub sum DUP comb.Java:
import java.util.*;
public class SubSumDupComb {
/**
* Find shortest combination add to given sum.
*
* @param arr input array,
* @param sum target sum,
* @return
*/
public static int[] find(int[] arr, int sum) {
// System.out.printf("input arr: %s, sum: %d\n", Arrays.toString(arr), sum);
List<Integer> list = find(arr, 0, sum, new ArrayList<>());
// System.out.printf("result: %s\n", list);
return listToArray(list);
}
/**
* Find shortest combination add to given sum, start from given index.
*
* @param arr input array,
* @param start start index, for further search,
* @param sum remain sum,
* @param prefixList prefix list,
* @return
*/
private static List<Integer> find(int[] arr, int start, int sum, List<Integer> prefixList) {
if (sum == 0) return prefixList; // base case,
if (start >= arr.length || sum < 0) return null; // bad case,
// exclude current index,
List<Integer> shortestExcludeList = find(arr, start + 1, sum, prefixList);
// include current index,
List<Integer> includePrefixList = new ArrayList<>(prefixList);
includePrefixList.add(arr[start]);
List<Integer> shortestIncludeList = find(arr, start, sum - arr[start], includePrefixList);
if (shortestIncludeList == null && shortestExcludeList == null) return null; // both null,
if (shortestIncludeList != null && shortestExcludeList != null) // both non-null,
return shortestIncludeList.size() < shortestExcludeList.size() ? shortestIncludeList : shortestExcludeList; // prefer to include elements with larger index,
else return shortestIncludeList == null ? shortestExcludeList : shortestIncludeList; // exactly one null,
}
/**
* Find shortest combination add to given sum, with cache.
*
* @param arr input array,
* @param sum target sum,
* @return
*/
public static int[] findWithCache(int[] arr, int sum) {
// System.out.printf("input arr: %s, sum: %d\n", Arrays.toString(arr), sum);
List<Integer> list = findWithCache(arr, 0, sum, new ArrayList<>(), new HashMap<>());
// System.out.printf("result: %s\n", list);
return listToArray(list);
}
/**
* Find shortest combination add to given sum, start from given index, with cache.
*
* @param arr input array,
* @param start start index, for further search,
* @param sum remain sum,
* @param prefixList prefix list,
* @return
*/
private static List<Integer> findWithCache(int[] arr, int start, int sum, List<Integer> prefixList, Map<Integer, Map<Integer, List<Integer>>> cache) {
if (sum == 0) return prefixList; // base case,
if (start >= arr.length || sum < 0) return null; // bad case,
// check cache,
Map<Integer, List<Integer>> cacheAtStart;
if ((cacheAtStart = cache.get(start)) != null && cacheAtStart.containsKey(sum)) { // cache hit, tips: the cashed list could be null, which indicate no result,
// System.out.printf("hit cache: start = %d, sum = %d, cached list: %s\n", start, sum, cacheAtStart.get(sum));
return cacheAtStart.get(sum);
}
// exclude current index, tips: should call this first,
List<Integer> shortestExcludeList = findWithCache(arr, start + 1, sum, prefixList, cache);
// include current index,
List<Integer> includePrefixList = new ArrayList<>(prefixList);
includePrefixList.add(arr[start]);
List<Integer> shortestIncludeList = findWithCache(arr, start, sum - arr[start], includePrefixList, cache);
List<Integer> resultList;
if (shortestIncludeList == null && shortestExcludeList == null) resultList = null; // both null,
else if (shortestIncludeList != null && shortestExcludeList != null) // both non-null,
resultList = shortestIncludeList.size() < shortestExcludeList.size() ? shortestIncludeList : shortestExcludeList; // prefer to include elements with larger index,
else
resultList = (shortestIncludeList == null ? shortestExcludeList : shortestIncludeList); // exactly one null,
// add to cache,
if (cacheAtStart == null) { // init cache at given start,
cacheAtStart = new HashMap<>();
cache.put(start, cacheAtStart);
}
cacheAtStart.put(sum, resultList == null ? null : resultList); // add this result to cache,
// System.out.printf("add cache: start = %d, sum = %d, list: %s\n", start, sum, resultList);
return resultList;
}
/**
* List to array.
*
* @param list
* @return
*/
private static int[] listToArray(List<Integer> list) {
if (list == null) return null; // no solution,
// list to array,
int[] result = new int[list.size()];
for (int i = 0; i < list.size(); i++) {
result[i] = list.get(i);
}
return result;
}
}
SubSumDupCombTest.java：
（测试用例，通过TestNG）
import org.testng.Assert;
import org.testng.annotations.BeforeClass;
import org.testng.annotations.Test;
import java.util.Arrays;
public class SubSumDupCombTest {
private int[] arr;
private int sum;
private int[] expectedResultArr;
private int[] arr2;
private int sum2;
private int sum2NoSolution;
private int[] expectedResultArr2;
@BeforeClass
public void setUp() {
// init - arr,
arr = new int[]{1, 4, 10, 20, 35};
sum = 17;
expectedResultArr = new int[]{1, 4, 4, 4, 4};
Arrays.sort(expectedResultArr);
// init - arr2,
arr2 = new int[]{14, 6, 10};
sum2 = 40;
sum2NoSolution = 17;
expectedResultArr2 = new int[]{10, 10, 10, 10};
Arrays.sort(expectedResultArr2);
}
@Test
public void test_find() {
// arr
int[] resultArr = SubSumDupComb.find(arr, sum);
Arrays.sort(resultArr);
Assert.assertTrue(Arrays.equals(resultArr, expectedResultArr));
// arr2
int[] resultArr2 = SubSumDupComb.find(arr2, sum2);
Arrays.sort(resultArr2);
Assert.assertTrue(Arrays.equals(resultArr2, expectedResultArr2));
}
@Test
public void test_find_noSolution() {
Assert.assertNull(SubSumDupComb.find(arr2, sum2NoSolution));
}
@Test
public void test_findWithCache() {
// arr
int[] resultArr = SubSumDupComb.findWithCache(arr, sum);
Arrays.sort(resultArr);
Assert.assertTrue(Arrays.equals(resultArr, expectedResultArr));
// arr2
int[] resultArr2 = SubSumDupComb.findWithCache(arr2, sum2);
Arrays.sort(resultArr2);
Assert.assertTrue(Arrays.equals(resultArr2, expectedResultArr2));
}
@Test
public void test_findWithCache_noSolution() {
Assert.assertNull(SubSumDupComb.findWithCache(arr2, sum2NoSolution));
}
}
说明：
find() //由递归方法堆栈使用，
哪里：
O(t^n)，是元素的平均时间。O(n)
为每对t使用缓存。
Compleixty：
时间:: findWithCache()
空间：(start, sum) //由缓存和递归方法堆栈使用，
哪里：
O(n * s)，是中间可能的总和。提示：