把一个数组分为两部分使得其和相差最小——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

相关文章

网页解析 lxml 库--实战

lxml库使用流程 lxml 是 Python 的第三方解析库,完全使用 Python 语言编写,它对 XPath表达式提供了良好的支 持,因此能够了高效地解析 HTML/XML 文档。本节讲解如何通过 lxml 库解析 HTML 文档。 pip install lxml lxm| 库提供了一个 etree 模块,该模块专门用来解析 HTML/XML 文档,下面来介绍一下 lxml 库

JVM 的类初始化机制

前言 当你在 Java 程序中new对象时,有没有考虑过 JVM 是如何把静态的字节码(byte code)转化为运行时对象的呢,这个问题看似简单,但清楚的同学相信也不会太多,这篇文章首先介绍 JVM 类初始化的机制,然后给出几个易出错的实例来分析,帮助大家更好理解这个知识点。 JVM 将字节码转化为运行时对象分为三个阶段,分别是:loading 、Linking、initialization

Spring Security 基于表达式的权限控制

前言 spring security 3.0已经可以使用spring el表达式来控制授权,允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true (Spring security默认会带有ROLE_前缀),去

浅析Spring Security认证过程

类图 为了方便理解Spring Security认证流程,特意画了如下的类图,包含相关的核心认证类 概述 核心验证器 AuthenticationManager 该对象提供了认证方法的入口,接收一个Authentiaton对象作为参数; public interface AuthenticationManager {Authentication authenticate(Authenti

Spring Security--Architecture Overview

1 核心组件 这一节主要介绍一些在Spring Security中常见且核心的Java类,它们之间的依赖,构建起了整个框架。想要理解整个架构,最起码得对这些类眼熟。 1.1 SecurityContextHolder SecurityContextHolder用于存储安全上下文(security context)的信息。当前操作的用户是谁,该用户是否已经被认证,他拥有哪些角色权限…这些都被保

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明(认真看哦) AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证,则会调用 #attemptAuthentica

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门(一):登录与退出》 《Spring-Security-入门(二):基于数据库验证》 《Spring-Security-入门(三):密码加密》 《Spring-Security-入门(四):自定义-Filter》 《Spring-Security-入门(五):在 Sprin

Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式Factory工厂模式Singleton单例模式Delegate委派模式Strategy策略模式Prototype原型模式Template模板模式 Spring5 beans 接口实例化代理Bean操作 Context Ioc容器设计原理及高级特性Aop设计原理Factorybean与Beanfactory Transaction 声明式事物

Java进阶13讲__第12讲_1/2

多线程、线程池 1.  线程概念 1.1  什么是线程 1.2  线程的好处 2.   创建线程的三种方式 注意事项 2.1  继承Thread类 2.1.1 认识  2.1.2  编码实现  package cn.hdc.oop10.Thread;import org.slf4j.Logger;import org.slf4j.LoggerFactory

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu