欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

把一个整数数组,分成个大小相同的子数组

程序员文章站 2022-03-10 12:09:24
...

今天有个人问我题目,大概就是要把一个整数数组,分成个大小相同的子数组

做不到的话就返回null

思想:

 额感觉是01背包的变种
先累加和,然后得到和的一半
每个物体的体积是数的大小
然后尽可能装满背包
dp方程:f[i][V] = max(f[i-1][V-v[i]]+v[i], f[i-1][V] )

import java.util.*;
public class divide {
    public static void main(String[] args) {
        int[] array = {2 ,3, 4 ,1 ,6 };
        ArrayList<Integer> list=getMaxDiff(array);
        if(list!=null){
            for(int i=0;i<list.size();i++){
                System.out.print(array[list.get(i)-1]);
                System.out.print(" ");
            }
        }else{
            System.out.print("null");
        }
    }

    public static ArrayList<Integer> getMaxDiff(int[] arr) {
        int len = arr.length;
        int sum = 0;
        for (int i = 0; i < len; i++)
            sum += arr[i];
        if(sum%2!=0)return null;
        int[][] dp = new int[len + 1][sum / 2 + 1];
        ArrayList<Integer> list=new ArrayList<>();
        for(int i=1;i<len+1;i++){
            for(int j=1;j<sum/2+1;j++){
                //if(dp[i-1][j]+arr[i-1]>dp[i-1][j]&&dp[i-1][j]+arr[i-1]<=j){
                if(j-arr[i-1]>=0&&dp[i-1][j-arr[i-1]]+arr[i-1]>dp[i-1][j]){
                    dp[i][j]=dp[i-1][j-arr[i-1]]+arr[i-1];
                }else{
                    dp[i][j]=dp[i-1][j];
                }
            }
        }





        int mcount=len;
        if(dp[len][sum/2]!=sum/2)return null;
        for(int j=sum/2;j>=0;){
            if(dp[mcount][j]!=dp[mcount-1][j]){
                list.add(mcount);
                j=j-arr[mcount-1];
                mcount--;
            }else {
                mcount--;
            }
            if(mcount==0){
                break;
            }
        }
        return list;
    }
}