【运筹优化】子集和问题(Subset Sum Problems , SSP)介绍 + 动态规划求解 + Java代码实现

本文主要是介绍【运筹优化】子集和问题(Subset Sum Problems , SSP)介绍 + 动态规划求解 + Java代码实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 一、问题介绍
  • 二、动态规划求解思路
  • 三、Java代码实现


一、问题介绍

子集和问题(Subset Sum Problems , SSP),它是复杂性理论中最重要的问题之一。

SSP会给定一组整数 a 1 , a 2 , . . . . , a n a_1,a_2,....,a_n a1,a2,....,an ,最多 n n n 个整数,我们需要判断是否存在一个非空子集,使得子集的总和为 M M M 整数?如果存在则需要输出该子集。

例如,集合给定为 [ 5 , 2 , 1 , 3 , 9 ] [5,2,1,3,9] [5,2,1,3,9] ,子集之和为 9 9 9 ;答案是肯定的,因为子集 [ 5 , 3 , 1 ] [5,3,1] [5,3,1] 的总和等于 9 9 9

这是一个 N P NP NP 完全问题。是背包的特殊情况。

在这里插入图片描述

目的: 给定一组正整数和一个值 S 总和,找出数组中是否存在一个子集,其总和等于给定的总和 S。


二、动态规划求解思路

设 A 是包含“n”个非负整数的数组或集合。找到集合“A”的子集“x”,使得 x 的所有元素的总和等于 w,其中 x 是另一个输入(总和)。

例如:

A = [2, 3, 5, 7, 10]

总和 (w) = 14

首先,我们创建一个表。该列包含从 0 到 14 的值,而行包含给定集合的元素,如下所示:

在下表中:

i :它表示行。行表示元素。

j :它表示列。列表示总和。

在这里插入图片描述
我们将使用 1 作为真值,使用 0 作为假值。值 1 位于 0 和 2 列下,如下所示:

这里 i=1, a[i] =2

注:每列的填充规则如下:
所需总和 = j - 元素
A[i][j] = A[i-1][所需总和]

当 j = 1

所需总和 = 1 - 2 = -1;由于总和为负,因此如上表所示,在第 1 列下输入 0。

当 j = 2

所需总和 = 2 - 2 = 0;由于 sum 的值为零,因此我们将 1 放在第 2 列下,如上表所示。

我们将 0 放在总和大于 2 的列下,因为我们不能从元素 2 中得出总和超过 2。

考虑要素 3。

这里 i = 2, a[i] = 3

在这里插入图片描述
总和小于 3 的列将具有与前几列相同的值。

当 j = 3 时,总和 [j] = 3

所需总和 = 3 -3 = 0;由于总和为零,因此我们将 1 放在第 3 列下,如上表所示。

当 j = 4;总和[j] = 4

所需总和 = 4 - 3 = 1;由于总和为 1,因此我们移至前一行,即 i=1 和 j=1。a[1][1] 处的值为 0,因此我们将 0 放在 a[2][4] 处。

当 j = 5 时,总和 [j] = 5

所需总和 = 5 -3 = 2;sum 的值为 2,因此 a[1][2] 处的值等于 1。因此,a[2][5] 处的值将为 1。

当 j = 6 时,总和 [j] = 6

所需总和 = 6 -3 = 3;sum 的值为 3,因此 a[1][3] 处的值等于 0。因此,a[2][6] 处的值将为 0。

当 j = 7 时,总和 [7] = 7

所需总和 = 7 - 3 = 4;sum 的值为 4,因此 a[1][4] 处的值等于 0。因此,a[2][7] 处的值将为 0。

这样,我们从第 8 列到 14 列中获取值 0。

考虑要素 5。

这里 i=3, a[i] = 5

在这里插入图片描述
总和小于 5 的列将具有与前几列相同的值。

当 j = 5 时,总和 [j] = 5

所需总和 = 5-5 = 0;由于总和的值为 0;因此,A[2][5] 处的值等于 1。

当 j = 6 时,总和 [j] = 6

所需总和 = 6-5 = 1;sum 的值为 1,因此 a[2][1] 处的值等于 0;因此,a[3][6] 处的值等于 0。

当 j=7 时,总和 [j] = 7

所需总和 = 7-5 = 2;sum 的值为 2,因此 a[2][2] 处的值等于 1;因此,a[3][7] 处的值等于 1。

当 j=8 时,总和 [j] = 8

所需总和 = 8-5 = 3;sum 的值为 3,因此 a[2][3] 处的值等于 1;因此,a[3][8] 处的值等于 1。

当 j=9 时,总和 [j] =9

所需总和 = 9-5 = 4;sum 的值为 4,因此 a[2][4] 处的值等于 0;因此,a[3][9] 处的值等于 0。

这样,我们从第 10 列到 14 列中获取值。

考虑要素 7。

这里 i=4, a[i] =7

在这里插入图片描述
总和小于 7 的列将具有与前几列相同的值。

当 j=9 时,总和 [j] = 9

所需总和 = 9 - 7 = 2;sum 的值为 2,因此 a[3][2] 处的值等于 1;因此,a[4][9] 处的值等于 1。

当 j=10 时,总和 [j] = 10

所需总和 = 10 - 7= 3;sum 的值为 3,因此 a[3][3] 处的值等于 1;因此,a[4][10] 处的值等于 1。

当 j=11 时,总和 [j] =11

所需总和 = 11-7 = 4;sum 的值为 4,因此 a[3][4] 处的值等于 0;因此,a[4][11] 处的值等于 0。

当 j=12 时,总和 [j] = 12

所需总和 = 12-7 = 5;sum 的值为 5,因此 a[3][5] 处的值等于 1;因此,a[4][12] 处的值等于 1。

当 j=13 时,总和 [j] =13

所需总和 = 13 - 7 = 6;sum 的值为 6,因此 a[3][6] 处的值等于 0;因此,a[4][13] 处的值等于 0。

当 j=14 时,总和 [j] = 14

所需总和 = 14 - 7 = 7;sum 的值为 7,因此 a[3][7] 处的值等于 1;因此,a[4][14] 处的值等于 1。

考虑元素 10

这里 i=5, a[i] = 10

在这里插入图片描述

总和小于 10 的列将具有与前几列相同的值。

当 j = 10 时,总和 [j] = 10

所需总和 = 10 - 10 = 0;sum 的值为 0,因此 a[4][0] 处的值等于 1;因此,a[5][10] 处的值等于 1。

当 j = 11 时,总和 [j] = 11

所需总和 = 11 - 10 = 1;总和的值为 1,因此 a[4][1] 处的值等于 0;因此,a[5][11] 处的值等于 0。

当 j=12 时,总和 [j] = 12

所需总和 = 12-10 = 2;sum 的值为 2,因此 a[4][2] 处的值等于 1;因此,A[5][12] 处的值等于 1。

当 j=13 时,总和 [j] = 13

所需总和 = 13 - 10 = 3;sum 的值为 3,因此 a[4][3] 处的值等于 1;因此,a[5][13] 处的值等于 1。

为了确定上述给定的问题是否包含子集,我们需要检查最后一行和最后一列。如果值为 1,则表示至少存在一个子集。

我们基本上遵循三个条件,在表的单元格中写入 1:
• A[i] = j
• A[i-1][j] = 1
• A[i-1][j-A[i]] = 1


三、Java代码实现

测试案例

A = {2, 3, 5, 7, 10}
sum = 14

Java代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;/*** @Author:WSKH* @ClassName:SSP_DP* @ClassType:* @Description:* @Date:2022/12/18/18:42* @Email:1187560563@qq.com* @Blog:https://blog.csdn.net/weixin_51545953?type=blog*/
public class SSP_DP {public static void main(String[] args) {int sum = 14;int[] arr = new int[]{2, 3, 5, 7, 10};long s = System.currentTimeMillis();new SSP_DP().solve(arr, sum);System.out.println("用时: " + (System.currentTimeMillis() - s) / 1000d + " s");}static int totalWei = 32;static int arrLength;public void solve(int[] arr, int sum) {// 如果sum=0直接返回空集if (sum == 0) {System.out.println(new ArrayList<>());return;}// 深拷贝数组arr = arr.clone();// 升序排序数组Arrays.sort(arr);SubSolution[] dp = new SubSolution[sum + 1];arrLength = arr.length;for (int rowIndex = 0; rowIndex < arr.length; rowIndex++) {if (arr[rowIndex] > sum) {break;}// 遍历上一层除了0位置外,有1的位置if (rowIndex > 0) {for (int colIndex = sum - arr[rowIndex]; colIndex >= 1; colIndex--) {if (dp[colIndex] != null) {if (dp[colIndex + arr[rowIndex]] == null) {dp[colIndex + arr[rowIndex]] = new SubSolution(dp[colIndex].flag, rowIndex);}}}}// 将刚好等于的位置赋值if (dp[arr[rowIndex]] == null) {dp[arr[rowIndex]] = new SubSolution(rowIndex);}for (SubSolution subSolution : dp) {System.out.print((subSolution == null ? 0 : 1) + ",");}System.out.println();}if (dp[sum] != null) {int checkSum = 0;List<Integer> valueList = new ArrayList<>();for (int i = 0; i < arr.length; i++) {if ((dp[sum].flag[i / totalWei] & (1 << (i % totalWei))) != 0) {valueList.add(arr[i]);checkSum += arr[i];}}if (checkSum != sum) {throw new RuntimeException(valueList + " 的和不等于 " + sum);}System.out.println(valueList);} else {System.out.println(Arrays.toString(arr) + "中,没有和为" + sum + "的子集");}}public static class SubSolution {int[] flag;public SubSolution() {flag = new int[arrLength / totalWei + 1];}public SubSolution(int index) {flag = new int[arrLength / totalWei + 1];flag[index / totalWei] = (flag[index / totalWei] | (1 << index % totalWei));}public SubSolution(int[] flag, int index) {this.flag = flag.clone();this.flag[index / totalWei] = (this.flag[index / totalWei] | (1 << index % totalWei));}}}

输出

0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,1,1,0,1,0,0,0,0,0,0,0,0,0,
0,0,1,1,0,1,0,1,1,0,1,0,0,0,0,
0,0,1,1,0,1,0,1,1,1,1,0,1,0,1,
0,0,1,1,0,1,0,1,1,1,1,0,1,1,1,
[2, 5, 7]
用时: 0.002 s

这篇关于【运筹优化】子集和问题(Subset Sum Problems , SSP)介绍 + 动态规划求解 + Java代码实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Java中的String.valueOf()和toString()方法区别小结

《Java中的String.valueOf()和toString()方法区别小结》字符串操作是开发者日常编程任务中不可或缺的一部分,转换为字符串是一种常见需求,其中最常见的就是String.value... 目录String.valueOf()方法方法定义方法实现使用示例使用场景toString()方法方法

Java中List的contains()方法的使用小结

《Java中List的contains()方法的使用小结》List的contains()方法用于检查列表中是否包含指定的元素,借助equals()方法进行判断,下面就来介绍Java中List的c... 目录详细展开1. 方法签名2. 工作原理3. 使用示例4. 注意事项总结结论:List 的 contain

C#使用SQLite进行大数据量高效处理的代码示例

《C#使用SQLite进行大数据量高效处理的代码示例》在软件开发中,高效处理大数据量是一个常见且具有挑战性的任务,SQLite因其零配置、嵌入式、跨平台的特性,成为许多开发者的首选数据库,本文将深入探... 目录前言准备工作数据实体核心技术批量插入:从乌龟到猎豹的蜕变分页查询:加载百万数据异步处理:拒绝界面

MySQL双主搭建+keepalived高可用的实现

《MySQL双主搭建+keepalived高可用的实现》本文主要介绍了MySQL双主搭建+keepalived高可用的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,... 目录一、测试环境准备二、主从搭建1.创建复制用户2.创建复制关系3.开启复制,确认复制是否成功4.同

Java实现文件图片的预览和下载功能

《Java实现文件图片的预览和下载功能》这篇文章主要为大家详细介绍了如何使用Java实现文件图片的预览和下载功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... Java实现文件(图片)的预览和下载 @ApiOperation("访问文件") @GetMapping("

用js控制视频播放进度基本示例代码

《用js控制视频播放进度基本示例代码》写前端的时候,很多的时候是需要支持要网页视频播放的功能,下面这篇文章主要给大家介绍了关于用js控制视频播放进度的相关资料,文中通过代码介绍的非常详细,需要的朋友可... 目录前言html部分:JavaScript部分:注意:总结前言在javascript中控制视频播放

C#如何动态创建Label,及动态label事件

《C#如何动态创建Label,及动态label事件》:本文主要介绍C#如何动态创建Label,及动态label事件,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#如何动态创建Label,及动态label事件第一点:switch中的生成我们的label事件接着,

Spring Boot + MyBatis Plus 高效开发实战从入门到进阶优化(推荐)

《SpringBoot+MyBatisPlus高效开发实战从入门到进阶优化(推荐)》本文将详细介绍SpringBoot+MyBatisPlus的完整开发流程,并深入剖析分页查询、批量操作、动... 目录Spring Boot + MyBATis Plus 高效开发实战:从入门到进阶优化1. MyBatis

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

Java并发编程必备之Synchronized关键字深入解析

《Java并发编程必备之Synchronized关键字深入解析》本文我们深入探索了Java中的Synchronized关键字,包括其互斥性和可重入性的特性,文章详细介绍了Synchronized的三种... 目录一、前言二、Synchronized关键字2.1 Synchronized的特性1. 互斥2.