【运筹优化】子集和问题(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保证HashMap线程安全的几种方式

《JAVA保证HashMap线程安全的几种方式》HashMap是线程不安全的,这意味着如果多个线程并发地访问和修改同一个HashMap实例,可能会导致数据不一致和其他线程安全问题,本文主要介绍了JAV... 目录1. 使用 Collections.synchronizedMap2. 使用 Concurren

Java Response返回值的最佳处理方案

《JavaResponse返回值的最佳处理方案》在开发Web应用程序时,我们经常需要通过HTTP请求从服务器获取响应数据,这些数据可以是JSON、XML、甚至是文件,本篇文章将详细解析Java中处理... 目录摘要概述核心问题:关键技术点:源码解析示例 1:使用HttpURLConnection获取Resp

python实现svg图片转换为png和gif

《python实现svg图片转换为png和gif》这篇文章主要为大家详细介绍了python如何实现将svg图片格式转换为png和gif,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录python实现svg图片转换为png和gifpython实现图片格式之间的相互转换延展:基于Py

Python利用ElementTree实现快速解析XML文件

《Python利用ElementTree实现快速解析XML文件》ElementTree是Python标准库的一部分,而且是Python标准库中用于解析和操作XML数据的模块,下面小编就来和大家详细讲讲... 目录一、XML文件解析到底有多重要二、ElementTree快速入门1. 加载XML的两种方式2.

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

redis过期key的删除策略介绍

《redis过期key的删除策略介绍》:本文主要介绍redis过期key的删除策略,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录第一种策略:被动删除第二种策略:定期删除第三种策略:强制删除关于big key的清理UNLINK命令FLUSHALL/FLUSHDB命

C++如何通过Qt反射机制实现数据类序列化

《C++如何通过Qt反射机制实现数据类序列化》在C++工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作,所以本文就来聊聊C++如何通过Qt反射机制实现数据类序列化吧... 目录设计预期设计思路代码实现使用方法在 C++ 工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作。由于数据类

usb接口驱动异常问题常用解决方案

《usb接口驱动异常问题常用解决方案》当遇到USB接口驱动异常时,可以通过多种方法来解决,其中主要就包括重装USB控制器、禁用USB选择性暂停设置、更新或安装新的主板驱动等... usb接口驱动异常怎么办,USB接口驱动异常是常见问题,通常由驱动损坏、系统更新冲突、硬件故障或电源管理设置导致。以下是常用解决

Python实现图片分割的多种方法总结

《Python实现图片分割的多种方法总结》图片分割是图像处理中的一个重要任务,它的目标是将图像划分为多个区域或者对象,本文为大家整理了一些常用的分割方法,大家可以根据需求自行选择... 目录1. 基于传统图像处理的分割方法(1) 使用固定阈值分割图片(2) 自适应阈值分割(3) 使用图像边缘检测分割(4)

Android实现在线预览office文档的示例详解

《Android实现在线预览office文档的示例详解》在移动端展示在线Office文档(如Word、Excel、PPT)是一项常见需求,这篇文章为大家重点介绍了两种方案的实现方法,希望对大家有一定的... 目录一、项目概述二、相关技术知识三、实现思路3.1 方案一:WebView + Office Onl