给定目标的5的倍数求和

Question

给定目标的5的倍数求和

javaalgorithm

3

可能是重复问题：
Java：将组中的5的倍数求和到给定目标大家好，

我正在努力解决以下问题，但没有正确的思路。

编写一个Java函数，给定一个整数数组，能否选择其中一些整数组成一个组，使得该组的总和等于给定的目标，并满足以下附加条件：数组中所有的5的倍数必须包含在该组中。如果紧随5的倍数后面的值为1，则不能选择它。

下面是一些测试用例：

groupSum5(0, {2, 5, 10, 4}, 19) → true groupSum5(0, {2, 5, 10, 4}, 17) → true groupSum5(0, {2, 5, 10, 4}, 12) → false groupSum5(0, {3, 5, 1}, 5) → true groupSum5(0, {3, 5, 1}, 4) → false

函数签名为 public boolean groupSum5(int start, int[] nums, int target)。

我已经编写了部分代码，但有一些测试用例无法通过。

     public boolean groupSum5(int start, int[] nums, int target) {     
           start = 0;     
           boolean flag = false;     
           for(int i=0;i<nums.length;i++){     
             if(nums[i]%5==0){     
                  start+=nums[i];                   
             }else if((start != target) && (start%5==0)){     
                  start+=nums[i];       
             }else if(start == target){      
                  flag = true;      
                  return flag;     
             }else if((nums[i]%5==0) && (nums[i+1]==1)){      
                  continue;                
             }    
           }
            return flag;      
     }

即使编写了这段代码，所有测试用例仍然失败。我已经挣扎了很长时间，但无法解决问题。

编辑：DIANTE，请提供代码修复，因为我已经尝试了这么多，不知道该怎么继续。

- deepakl.2000

2

请提出具体问题，而不是泛泛而谈的“帮我”。 - Gabe

1

请注意，您不需要50个声望点来发表所有评论，只需要在您没有直接参与的评论中才需要。您始终可以对自己的问题和答案以及您提出的任何问题的答案进行评论，即使只有1个声望点。 - sarnold

虽然我们喜欢帮助人们解决作业问题，但我们避免提供作业答案——这是你需要自己解决和努力的问题。你已经发布了一个开端，这很好 :) 但如果你仔细阅读@Dante的帖子，我认为你会发现它是一个很好的起点。@UBM的建议是不错的，但如果“动态规划”对你来说是一个新词，那么暂时不用担心。你明年就会理解的。 :) - sarnold

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user180100 · Accepted Answer

这里有一个解决方案，但请先查看讨论：

package so5987154;

import java.util.Collection;
import java.util.List;
import java.util.Set;

import com.google.common.collect.Lists;
import com.google.common.collect.Sets;

public class Summation {
    /**
     * Sum of start and every element of the collection.
     * 
     * @param start
     *            starting value for the sum
     * @param list
     *            Collection to sum.
     * @return the sum.
     */
    private int sum(final Integer start, final Collection<Integer> list) {
        int sum = start;

        for (final int i : list) {
            sum += i;
        }

        return sum;
    }

    /**
     * Given an array of ints, is it possible to choose a group of some of the ints, such that the group sums to the given target
     * with these additional constraints: all multiples of 5 in the array must be included in the group. If the value immediately
     * following a multiple of 5 is 1, it must not be chosen.
     * 
     * @param start
     *            not used
     * @param nums
     *            array of int (input)
     * @param target
     *            target value for the summation
     * @return true if we found a group that meet the criteria.
     */
    public boolean groupSum5(final int start, final int[] nums, final int target) {
        // list of values that need to be included (multiple of 5)
        final List<Integer> fixed = Lists.newArrayList();

        // list of value that can be included (anything but 1 preceded by a multiple of 5)
        final List<Integer> candidates = Lists.newArrayList();

        // fills candidates and fixed
        for (int i = 0; i < nums.length; i++) {
            final int cand = nums[i];

            if (cand == 1 && i > 0) {
                final int prev = nums[i - 1];
                if (prev % 5 != 0) {
                    candidates.add(cand);
                }
            } else if (cand % 5 == 0) {
                fixed.add(cand);
            } else if (cand <= target) {
                candidates.add(cand);
            }
        }

        // compute the sum of fixed
        final int sumFixed = sum(0, fixed);

        // if the sum of fixed is equals to target we don't need to do anything because
        // we already know we need to return true.
        if (sumFixed == target) {
            return true; // NOPMD
        }

        // if the sum of fixed is greater than target we don't need to do anything because
        // we already know we need to return false (all multiple of 5 must be included)
        // If candidates is empty there's no way we can achieve the desired goal.
        if (sumFixed <= target && !candidates.isEmpty()) {
            // generates all subsets of candidates:
            // { 1, 2 } => {}, {1}, {2}, {1, 2}
            final Set<Set<Integer>> powerSet = Sets.powerSet(Sets.newHashSet(candidates));

            // for each found subset, computes the sum of the subset and add it to the sum of
            // multiples of 5 then compare it to target. If equals => return true.
            for (final Set<Integer> set : powerSet) {
                if (sumFixed + sum(0, set) == target) {
                    return true; // NOPMD
                }
            }
        }

        return false;
    }
}

相关测试:

package so5987154.tests;

import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;

import org.junit.Test;

import so5987154.Summation;

@SuppressWarnings("PMD")
public class SummationTest {
    private final Summation s = new Summation();

    @Test
    public void testGroupSum5() {
        assertTrue(s.groupSum5(0, new int[] { 2, 5, 10, 4 }, 19));
        assertTrue(s.groupSum5(0, new int[] { 2, 5, 10, 4 }, 17));
        assertFalse(s.groupSum5(0, new int[] { 2, 5, 10, 4 }, 12));
        assertTrue(s.groupSum5(0, new int[] { 2, 5, 10, 4 }, 19));
        assertTrue(s.groupSum5(0, new int[] { 3, 5, 1 }, 5));
        assertFalse(s.groupSum5(0, new int[] { 3, 5, 1 }, 4));
        assertTrue(s.groupSum5(0, new int[] { 3, 1 }, 4));
        assertFalse(s.groupSum5(0, new int[] { 3, 1 }, 2));
        assertTrue(s.groupSum5(0, new int[] { 1 }, 1));
    }
}

但是，您的签名参数start表明了递归。首先，您可以从整数数组中删除以下内容：

所有5的倍数并将它们加起来放在start中
所有前面有5的倍数的1

然后用start和新的int数组调用您的方法。

在方法中，您需要：

检测start是否等于目标=>返回true
检测start是否超过目标=>返回false
检测数组是否为空=>返回false
调用带有start+x的方法，其中x是数组的一个元素，并且数组已经去掉了x=>返回所有结果的OR

例子：{2, 5, 10, 4}，目标=19

5的倍数之和：5+10 = 15, 前面没有5 => 新的数组{2, 4}

第一次调用：method(15, {2, 4}, 19)

start == target => NO
start > target => NO
array empty => NO
r1 = method(15+2, {4}, 19) and r2 = method(15+4, {2}, 19)

第二次调用(r1)：method(15+2, {4}, 19)

start == target => NO
start > target => NO
array empty => NO
r11 = method(15+2+4, {}, 19)

第三次调用(r11)：method(15+2+4, {}, 19)

start == target => NO
start > target => YES => false

第二次调用(r2)：method(15+4, {2}, 19)

start == target => YES => true

我们回到第一次调用，有r1 = r11 = false和r2 = true => return false OR true = true，结束。

您可以看到Sets.powerSet等同于递归调用r(k)。