把一个数组分为两部分使得其和相差最小——Java实现(详细注释,全面解析)

本文主要是介绍把一个数组分为两部分使得其和相差最小——Java实现(详细注释,全面解析),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

package bag;public class Test {/*** 给一个整数数组 array,把他分为两部分 a 和 b* 使得 a 和 b 的元素之和的差最小** @param array 输入数组* @return 返回差值最小是多少* <p>* 解析:array分出来的两个数组a、b之和sum1、sum2等于总和SUM* 既然要 sum1 与 sum2 之间相差最小则他们应该尽量接近 SUM/2* <p>* 即问题转变为:在array中取出数据存入a中,在不超过 SUM/2 的情况下使得a的总和最大* <p>* 也就是0-1背包问题*/public static int getTwoSubArrayMinDiff(int[] array) {int ans = 0;if (array.length == 0)return ans;int n = array.length;int SUM = 0;for (int i = 0; i < n; i++) {SUM += array[i];}// 状态转移方程:设待选的各个数据为 i,容量为 SUM/2,// dp[i][c] = max( dp[i-1][c], dp[i-1][C-c[i]] + c[i])/*解释:c 就是 capacity,每次从array里面取走一个数据,存在: 放入新数组a里面和不放入新数组里面a 两个选择不管是否放入i值都少了一个:i-1* 放入的时候:不仅要给 i 值减一,且将a中剩余可存入的数量减少响应值,即 C-c[i] (总容量减去已存入的等于剩余的)* 不放入的时候:仅需将i减一即可那么以上两种情况选择哪一种会导致a的和最接近 SUM/2 呢?使用max取本次dp[i][c]的最大值即可*/int[][] dp = new int[n + 1][SUM / 2 + 1];/*本题并不完全是一个背包问题,这里没有价值只有重量,也就是每一个数组元素的值。外层循环从0开始也行从1开始也行,注意别越界就可以了,内层循环每来一次,就得重新计算 dp[i][1...C] 的值,内层循环的含义是:每次从array里面拿到一个数据后要考虑是否放到新数组a里面,那么就得计算该元素放入是否能加入到a以及能否获取最大收益。最终不管是否加入了a,该元素都不再考虑。那么内层循环里面通过不断改变背包的容量(从1到SUM/2)来确定是否能产生最大收益*/for (int i = 0; i < n; i++) {for (int j = 1; j <= SUM / 2; j++) { // 假设当前的背包容量是 j// 这是不放入背包的情况dp[i + 1][j] = dp[i][j];// 这是放入背包的情况if (array[i] <= j // 先要确保array[i]的值不能大于背包容量&& dp[i][j - array[i]] + array[i] > dp[i][j]) { // 然后可以放心的把当前物品放入背包dp[i + 1][j] = dp[i][j - array[i]] + array[i];}// dp[i + 1][j] 会得到一个最大值}}// dp[n][SUM / 2] 是新数组a的和,他的两倍应该近似于SUM,差值即为两个新数组a、b之间的和最小差return SUM - 2 * dp[n][SUM / 2];}public static void main(String[] args) {
//        int[] array = {2, 3, 4, 6};
//        int[] array = {5, 6, 8, 7};int[] array = {25, 0, 18, 3, 9, 4, 12, 7, 6, 11};System.out.println(getTwoSubArrayMinDiff(array));System.out.println(getTwoSubArrayMinDiff2(array));}public static int getTwoSubArrayMinDiff2(int[] array) {if (array.length == 0) {return 0;}int sum = 0;for (int x : array) {sum += x;}int n = array.length;// 状态转移方程int[][] dp = new int[n][sum / 2 + 1];// 首先检查 0 号元素是否可以存入背包for (int i = 0; i <= sum / 2; i++ ) {dp[0][i] = (i >= array[0]) ? array[0] : 0;}// 然后再动态规划处理for (int i = 1; i < n; i++) {for (int j = 0; j <= sum / 2; j++) {dp[i][j] = dp[i - 1][j];// 若剩余空间可以存入当前的array[i]if (j >= array[i]) {dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - array[i]] + array[i]);}}}return sum - 2 * dp[n - 1][sum / 2];}
}

这篇关于把一个数组分为两部分使得其和相差最小——Java实现(详细注释,全面解析)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1004002

相关文章

mybatis执行insert返回id实现详解

《mybatis执行insert返回id实现详解》MyBatis插入操作默认返回受影响行数,需通过useGeneratedKeys+keyProperty或selectKey获取主键ID,确保主键为自... 目录 两种方式获取自增 ID:1. ​​useGeneratedKeys+keyProperty(推

Spring Boot集成Druid实现数据源管理与监控的详细步骤

《SpringBoot集成Druid实现数据源管理与监控的详细步骤》本文介绍如何在SpringBoot项目中集成Druid数据库连接池,包括环境搭建、Maven依赖配置、SpringBoot配置文件... 目录1. 引言1.1 环境准备1.2 Druid介绍2. 配置Druid连接池3. 查看Druid监控

Linux在线解压jar包的实现方式

《Linux在线解压jar包的实现方式》:本文主要介绍Linux在线解压jar包的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux在线解压jar包解压 jar包的步骤总结Linux在线解压jar包在 Centos 中解压 jar 包可以使用 u

Java中读取YAML文件配置信息常见问题及解决方法

《Java中读取YAML文件配置信息常见问题及解决方法》:本文主要介绍Java中读取YAML文件配置信息常见问题及解决方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要... 目录1 使用Spring Boot的@ConfigurationProperties2. 使用@Valu

创建Java keystore文件的完整指南及详细步骤

《创建Javakeystore文件的完整指南及详细步骤》本文详解Java中keystore的创建与配置,涵盖私钥管理、自签名与CA证书生成、SSL/TLS应用,强调安全存储及验证机制,确保通信加密和... 目录1. 秘密键(私钥)的理解与管理私钥的定义与重要性私钥的管理策略私钥的生成与存储2. 证书的创建与

浅析Spring如何控制Bean的加载顺序

《浅析Spring如何控制Bean的加载顺序》在大多数情况下,我们不需要手动控制Bean的加载顺序,因为Spring的IoC容器足够智能,但在某些特殊场景下,这种隐式的依赖关系可能不存在,下面我们就来... 目录核心原则:依赖驱动加载手动控制 Bean 加载顺序的方法方法 1:使用@DependsOn(最直

SpringBoot中如何使用Assert进行断言校验

《SpringBoot中如何使用Assert进行断言校验》Java提供了内置的assert机制,而Spring框架也提供了更强大的Assert工具类来帮助开发者进行参数校验和状态检查,下... 目录前言一、Java 原生assert简介1.1 使用方式1.2 示例代码1.3 优缺点分析二、Spring Fr

java使用protobuf-maven-plugin的插件编译proto文件详解

《java使用protobuf-maven-plugin的插件编译proto文件详解》:本文主要介绍java使用protobuf-maven-plugin的插件编译proto文件,具有很好的参考价... 目录protobuf文件作为数据传输和存储的协议主要介绍在Java使用maven编译proto文件的插件

c++ 类成员变量默认初始值的实现

《c++类成员变量默认初始值的实现》本文主要介绍了c++类成员变量默认初始值,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录C++类成员变量初始化c++类的变量的初始化在C++中,如果使用类成员变量时未给定其初始值,那么它将被

Java中的数组与集合基本用法详解

《Java中的数组与集合基本用法详解》本文介绍了Java数组和集合框架的基础知识,数组部分涵盖了一维、二维及多维数组的声明、初始化、访问与遍历方法,以及Arrays类的常用操作,对Java数组与集合相... 目录一、Java数组基础1.1 数组结构概述1.2 一维数组1.2.1 声明与初始化1.2.2 访问