题解 | #数组分组#

问题 输入int型数组，询问该数组能否分成两组，使得两组中各元素加起来的和相等，并且，所有5的倍数必须在其中一个组中，所有3的倍数在另一个组中（不包括5的倍数），不是5的倍数也不是3的倍数能放在任意一组，可以将数组分为空数组，能满足以上条件，输出true；不满足时输出false

题解 分析： 将所有数组中元素和记为sum，是5的倍数的元素和记为sum5， 不是3的倍数也不是5的倍数的元素添加到数组nums中。则问题转化为问 在数组nums中是否可以选若干个元素，使得这若干个元素的和为sum/2 - sum5。若可以，输出true；否则输出false。 这么一分析，感觉有点和0-1背包问题相似 那么设dp(j,i)表示能否从nums中下标i到n-1选取若干个元素，使它们的和为j的解。有解为true，无则false。 那么就可以写出递归关系： dp(j,i) = dp(j,i+1)||dp(j-nums[i],i+1). 简单解释一下，若第i个元素不选，则dp(j,i) = dp(j,i+1)；若第i个元素选取，则dp(j,i) = dp(j-nums[i],i+1)； 那么边界条件就应该是： 当j=0,dp(j,i)=true; 当j=nums中下标i到n-1中任意个元素,dp(j,i)=true; 当i=n-1时，若nums[n-1]=j,则dp(j,i)=true;否则，dp(j,i)=false。

那么递归关系清楚了，就可以采取自底向上的动态规划算法或者直接递归。 先看递归：

import java.util.Scanner;
public class Maiin {
    public static void main(String[] args) {
        Scanner scn = new Scanner(System.in);
        while (scn.hasNext())
        {
            int n = scn.nextInt();
            int sum = 0;
            int sum5 = 0;
            ArrayList<Integer> nums = new ArrayList<Integer>();
            for (int i = 0; i < n; ++i) {
                int a = scn.nextInt();
                if (a % 5 == 0)
                {
                    sum5 += a;
                } else if (a % 3 != 0) {
                    nums.add(a);
                }
                sum += a;
            }
            if(sum % 2 != 0)
            {
                System.out.println("false");
            }
            else
            {
                System.out.println(dp(sum/2-sum5,0,nums));
            }
        }
    }

    public static boolean dp(int j, int i, ArrayList<Integer> nums) {
        if (j==0)
        {
            return true;
        }
        if(i == nums.size() - 1)
        {
            if (nums.get(i) == j)
            {
                return true;
            }
            else
            {
                return false;
            }
        }
        if (i >= nums.size())
        {
            return false;
        }
        return dp(j, i + 1, nums) || dp(j - nums.get(i), i + 1, nums);

    }
}

最坏情况下，时间复杂度O(2^n)

再看动态规划

#include<vector>
#include<algorithm>

using namespace std;

bool dp(vector<int> &num, int t,int k)
{
    if (t==0 && k==num.size()) return true;
    if (k==num.size()) return false;
    //如果只是3的倍数，不能加到该集合中。
    if (!(num[k]%3)) return(dp(num,t,k+1));
    if (num[k]==t) return true;
    //对于一个数有两种选择，加或者不加到该集合中
    return(dp(num,t-num[k],k+1)|dp(num,t,k+1));
}

int main()
{
    int n;
    while(cin>>n)
    {
        vector<int> num;
        int x,sum=0,part=0;//只要找到总和的一半即可，剩下的数字之和自然为总和的一半。
        for (int i=0;i<n;i++)
        {
            cin>>x;
            //如果是5的倍数，不放入数组num
            if (x%5)
                num.push_back(x);
            else
                part += x;
            sum += x;
        }
        //如果所有数之和不是偶数，则肯定是false
        if (sum%2)
        {
            cout<<"false"<<endl;
        }
        else
        {
            sum = sum/2;
            if (dp(num,sum-part,0))
                cout<<"true"<<endl;
            else cout<<"false"<<endl;
        }
        
        num.clear();
    }
}

其实还有一种取巧的方法： 根据题意直接可以知道：5的倍数的元素和 - 3的倍数的元素和 + 其他元素的加加减减 = 0。 那么将其他元素取绝对值再升序排列成数组nums，设当前值sum = 5的倍数的元素和 - 3的倍数的元素和，那么由于已经排列的元素具有单调性，从大到小依次去一个元素，根据sum的正负决定是加上还是减去该元素。最终看sum是否为0，即可。 需要注意的是，由于sum的初值和已经排列的元素之间没有单调关系，所以对于取出的第一个元素nums[n-1]不能确定是加上还是减去它，所以分开做两次同样的操作即可。 至于可以这样做的原理，应该可以通过严谨的数学推理证明，简单的说就是在于我们的目的是尽可能的对sum加上或者减去nums中的一个元素，尽可能的使sum向0靠近。 代码如下：

/*
取巧的方法
 */
import java.util.Arrays;
import java.util.Scanner;
import java.lang.Math;
public class Main {
    public static void main(String[] args) {
        Scanner scn = new Scanner(System.in);
        while (scn.hasNext())
        {
            int n = scn.nextInt();
            int[] nums = new int[n];
            int sum = 0;
            for (int i = 0; i < n; ++i) {
                int a =scn.nextInt();
                if (a %5 == 0)
                {
                    sum += a;
                }
                else  if (a %3 == 0)
                {
                    sum -= a;
                }
                else
                {
                    nums[i] = Math.abs(a);
                }
            }
            Arrays.sort(nums);
            int sum1 = sum;

            sum += nums[n - 1];
            for (int i = n - 2;i >= 0; --i)
            {
                if(nums[i] == 0)
                {
                    break;
                }
                if (sum <= 0)
                {
                    sum += nums[i];
                }
                else
                {
                    sum -= nums[i];
                }
            }

            sum1 -= nums[n - 1];
            for (int i = n - 2;i >= 0; --i)
            {
                if(nums[i] == 0)
                {
                    break;
                }
                if (sum1 <= 0)
                {
                    sum1 += nums[i];
                }
                else
                {
                    sum1 -= nums[i];
                }
            }
            System.out.println(sum * sum1 == 0 ? "true" : "false");

        }
    }
}