查找加起来等于给定总和的最小子数组(允许重复) [英] Finding the smallest sub-array that adds up to a given sum (Duplicates are allowed)

查看:31
本文介绍了查找加起来等于给定总和的最小子数组(允许重复)的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我想找到与给定目标相加的最小子数组.
我的输入是输入 array 和目标 sum.

I want to find the smallest sub-array that adds up to a given target.
My inputs are the an input array and the target sum.

我知道这个问题已经被问过很多次了,但在大多数情况下,人们试图找到每一个可能的组合,以达到他们的目标,或者他们的解决方案不允许重复.

I know this problem has been asked many times, but in most cases, people are trying to find every possible combination that adds up to their target or their solution does not allow duplicates.

就我而言,我想找到最小的子数组,并且允许从输入数组中复制数据.

In my case, I want to find only the smallest sub-array and duplicating data from the input array is allowed.

例如,给定 [1,4,10,20,35] 的输入数组和 17 的目标,我希望输出数组为[10,4,1,1,1].
因此,我的算法可以在查找输出时复制输入数组中的任何值.

For example, given an input array of [1,4,10,20,35] and a target of 17, I'd expect an output array of [10,4,1,1,1].
So my algorithm is allowed to duplicate any of the values from the input array in finding the output.

这是我目前所拥有的:

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 个目标上测试代码:

and just a simple driver to test the code on 100 targets:

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].
我明白为什么我的算法是错误的,但我不知道如何解决它.

I've implemented an O(n) algorithm that works for most values, but in some cases, I'm getting the wrong result.
For example, when I run my code with an input of [1,4,10,20,35,56,84], and a target sum of 69, the correct output would be [35,20,10,4] but my algorithm outputs [56,10,1,1,1].
I understand why my algorithm is wrong but I'm not sure how to fix it.

推荐答案

由于您使用的是 Java,我将在 Java 中添加一个实现,使用 动态编程 (在这种情况下是递归).

Since you are using Java, I would add an implementation in Java, using dynamic programming (it's recursion, in this case).

SubSumDupComb.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()
    这是纯粹的递归.
    复杂度:

  • find()
    It's pure recursion.
    Compleixty:

  • 时间::O(t^n)//在最坏的情况下,
  • 空格:O(n)//被递归方法栈使用,
  • Time:: O(t^n) // in worst case,
  • Space: O(n) // used by recursive method stack,

地点:

  • t,是包含元素的平均时间.
  • t, is average time of an element is included.

findWithCache()
对每对 (start, sum) 使用缓存.
复杂度:

findWithCache()
Use cache for each pair of (start, sum).
Compleixty:

  • 时间::O(n * s)
  • Space: O(n * s)//缓存使用,和递归方法栈,
  • Time:: O(n * s)
  • Space: O(n * s) // used by cache, and recursive method stack,

地点:

  • s,是中间可能和的计数.
  • s, is count of possible sum in the middle.

提示:

  • 当有多个可能的最短结果时,结果更喜欢具有较大索引的数字.

这篇关于查找加起来等于给定总和的最小子数组(允许重复)的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆