把一个整数数组,分成个大小相同的子数组
程序员文章站
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] )
先累加和,然后得到和的一半
每个物体的体积是数的大小
然后尽可能装满背包
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;
}
}
推荐阅读
-
给定一个整数数组 nums,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
-
Java实现给定一个无序的整数数组,找到其中最长上升子序列的长度。
-
在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
-
在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
-
java把正整数数组排成一个最小的数
-
php 把一个数组分成有n个元素的二维数组的算法
-
数组长度相同,怎么把一个数组的键名变成第二个数组的键值
-
如何把多个数组合并成一个数组,合并二维数组相同的key
-
如何把多个数组合并成一个数组,合并二维数组相同的key
-
[伸手党]求个function,传入一个规律的二维数组,每个子数组都是键名相同的数组,键值都是整数,返回结果是二维数组多了一个子数组,是每个子数组的求和结果