数组分成两个最接近集合问题

数组,分成,两个,接近,集合,问题 · 浏览次数 : 179

小编点评

**算法 1:暴力递归** ```java public static int splitSumClosed(int[] arr) { if (arr == null || arr.length < 2) { return 0; } int sum = 0; for (int num : arr) { sum += num; } int aim = sum / 2; return process(arr, 0, aim); } public static int process(int[] arr, int i, int rest) { if (i == arr.length) { return 0; } int p1 = process(arr, i + 1, rest); if (rest - arr[i] >= 0) { p1 = Math.max(process(arr, i + 1, rest - arr[i]) + arr[i], p1); } return p1; } ``` **算法 2:动态规划** ```java public static int splitSumClosed2(int[] arr) { if (arr == null || arr.length < 2) { return 0; } int sum = 0; for (int num : arr) { sum += num; } int aim = sum / 2; int[][] dp = new int[arr.length + 1][aim + 1]; // 初始化最后一行为 0 for (int i = arr.length - 1; i >= 0; i--) { for (int j = 0; j < aim + 1; j++) { dp[i + 1][j] = dp[i + 1][j]; } } // 从最后一行依次递推 for (int i = arr.length - 1; i >= 0; i--) { for (int j = 0; j < aim + 1; j++) { if (j - arr[i] >= 0) { dp[i + 1][j] = Math.max(dp[i + 1][j - arr[i]] + arr[i], dp[i + 1][j]); } } } return dp[0][aim]; } ``` **注意** * 两种算法都使用动态规划的思想,但算法 2 更能有效地处理数组长度较大的情况。 * 两种算法都使用递归来计算最接近的两个集合的累加和。

正文

数组分成两个最接近集合问题

作者:Grey

原文地址:

博客园:数组分成两个最接近集合问题

CSDN:数组分成两个最接近集合问题

问题描述

给定一个正数数组 arr, 请把 arr 中所有的数分成两个集合,尽量让两个集合的累加和接近;

返回:最接近的情况下,较小集合的累加和。

主要思路

首先把数组之和求出来,假设为 sum,那么sum/2就是累加和的一半,定义递归函数

int process(int[] arr, int i, int rest)

递归含义表示:数组 arr 从 i 开始,一直到最后,随意选取进行累加,得到的最接近 rest 且较小的集合的累加和。

接下来是 base case,i 到数组 arr 的结尾位置,显然返回 0。

if (i == arr.length) {
    return 0;
}

接下来是普遍位置

        int p1 = process(arr, i + 1, rest);
        if (rest - arr[i] >= 0) {
            p1 = Math.max(process(arr, i + 1, rest - arr[i]) + arr[i], p1);
        } 

其中 p1 表示:不选取 i 位置的值进行累加,得到的最接近 rest 且较小的集合的累加和。

process(arr, i + 1, rest - arr[i]) + arr[i]表示:选取了 i 位置的值进行累加,得到的最接近 rest 且较小的集合的累加和。

注:选取 i 位置的值进行累加有条件,即rest - arr[i] > 0,否则选取之后,会得到较大的那个集合的累加和。

递归方法的完整代码见(含对数器)


    public static int splitSumClosed(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        int sum = 0;
        for (int num : arr) {
            sum += num;
        }
        int aim = sum / 2;
        return process(arr, 0, aim);
    }

    public static int process(int[] arr, int i, int rest) {
        if (i == arr.length) {
            return 0;
        }
        int p1 = process(arr, i + 1, rest);
        if (rest - arr[i] >= 0) {
            p1 = Math.max(process(arr, i + 1, rest - arr[i]) + arr[i], p1);
        }
        return p1;
    }

以上暴力递归可以改成动态规划,由于递归函数的可变参数有两个,一个是 i,一个是 rest,且其变化范围是固定的,所以可以定义一个二维数组来存所有的递归过程值,

int[][] dp = new int[arr.length + 1][aim + 1];

接下来根据递归函数可知dp表的最后一行均为 0;

dp[i][rest]依赖于dp[i+1][rest]dp[i+1][rest - arr[i]]两个位置的值,所以整个 dp 表可以从最后一行开始依次往上递推。

      for (int i = arr.length - 1; i >= 0; i--) {
            for (int j = 0; j < aim + 1; j++) {
                int p1 = dp[i + 1][j];
                if (j - arr[i] >= 0) {
                    p1 = Math.max(dp[i + 1][j - arr[i]] + arr[i], p1);
                }
                dp[i][j] = p1;
            }
        }

动态规划方法完整代码如下

    public static int splitSumClosed2(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        int sum = 0;
        for (int num : arr) {
            sum += num;
        }
        int aim = sum / 2;
        int[][] dp = new int[arr.length + 1][aim + 1];
        // last row == 0
        for (int i = arr.length - 1; i >= 0; i--) {
            for (int j = 0; j < aim + 1; j++) {
                int p1 = dp[i + 1][j];
                if (j - arr[i] >= 0) {
                    p1 = Math.max(dp[i + 1][j - arr[i]] + arr[i], p1);
                }
                dp[i][j] = p1;
            }
        }
        return dp[0][aim];
    }

更多

算法和数据结构笔记

与数组分成两个最接近集合问题相似的内容:

数组分成两个最接近集合问题

数组分成两个最接近集合问题 作者:Grey 原文地址: 博客园:数组分成两个最接近集合问题 CSDN:数组分成两个最接近集合问题 问题描述 给定一个正数数组 arr, 请把 arr 中所有的数分成两个集合,尽量让两个集合的累加和接近; 返回:最接近的情况下,较小集合的累加和。 主要思路 首先把数组之

SpringBoot进阶教程(七十五)数据脱敏

无论对于什么业务来说,用户数据信息的安全性无疑都是非常重要的。尤其是在数字经济大火背景下,数据的安全性就显得更加重要。数据脱敏可以分为两个部分,一个是DB层面,防止DB数据泄露,暴露用户信息;一个是接口层面,有些UI展示需要数据脱敏,防止用户信息被人刷走了。 v需求背景 DB层面的脱敏今天先不讲,今

记一次asp.net 8 服务器爆满的解决过程

1.描述一下服务器配置: 一台2c4g的centos,做api接口反代 一台8c16g的windows 2019 作为实际服务器,跑了iis,sql server,mongodb,redis 2.业务描述 2.0 服务器分为两个站点:importapi:用于处理数据导入,,,webapi:用于处理对

[转帖] jq实现json文本对比

原创:打码日记(微信公众号ID:codelogs),欢迎分享,转载请保留出处。 简介# 近期,为了给一个核心系统减负,组内决定将一些调用量大的查询接口迁移到另一个系统,由于接口逻辑比较复杂,为了保证接口逻辑一致,我们决定将一周内的请求参数在两个接口重放,并用脚本校验两边接口的响应结果。接口返回数据是

使用spark-sql处理Doris大表关联

背景 最近项目上有一个需求,需要将两张表(A表和B表)的数据进行关联并回写入其中一张表(A表),两张表都是分区表,但是关联条件不包括分区字段。 分析过程 方案一 最朴素的想法,直接关联执行,全表关联,一条SQL搞定全部逻辑。想法越简单,执行越困难。由于数据量大,服务器规模较小,尽管各台服务器内存和C

测试员最佳跳槽频率是多少?进来看看你是不是符合

最近笔者刷到一则消息,一位测试员在某乎上分享,从月薪5K到如今的20K,他总共跳了10次槽,其中还经历过两次劳动申诉,拿到了大几万的赔偿,被同事们称为“职场碰瓷人”。 虽说这种依靠跳槽式的挣钱法相当奇葩,但不得不说,跳槽成为了职场上越来越常见的现象。在智联招聘调查数据中我们看到,93.2%的白领有跳

Redisson/Jedis 线程数不足报错问题的思考

Redisson/Jedis 线程数不足报错问题的思考 背景 最近公司内总出现 Redis相关的错误 !-_-! 看我最近发的博客就可以看的出来. 这个错误提示其实是 两年前 清明节进行 压测时发现的. 当时其实没有将这个问题细致分析下去. 最近学习的比较多. 感觉可以尝试分析一下这个问题. 报错的

记一次 .NET 某仪器测量系统 CPU爆高分析

一:背景 1. 讲故事 最近也挺奇怪,看到了两起 CPU 爆高的案例,且诱因也是一致的,觉得有一些代表性,合并分享出来帮助大家来避坑吧,闲话不多说,直接上 windbg 分析。 二:WinDbg 分析 1. CPU 真的爆高吗 这里要提醒一下,别人说爆高不一定真的就是爆高,我们一定要拿数据说话,可以

CutMix&Mixup详解与代码实战

摘要:本文将通过实践案例带大家掌握CutMix&Mixup。 本文分享自华为云社区《CutMix&Mixup详解与代码实战》,作者:李长安。 引言 最近在回顾之前学到的知识,看到了数据增强部分,对于CutMix以及Mixup这两种数据增强方式发现理解不是很到位,所以这里写了一个项目再去好好看这两种数

14.4 Socket 双向数据通信

所谓双向数据传输指的是客户端与服务端之间可以无差异的实现数据交互,此类功能实现的核心原理是通过创建`CreateThread()`函数多线程分别接收和发送数据包,这样一旦套接字被建立则两者都可以异步发送消息,本章将实现简单的双向交互功能。首先我们需要封装两个函数,这里`RecvFunction`函数用于接收数据,`SendFunction`函数则用于发送数据,这两段代码在服务端与客户端之间是一致的