search
HomeJavajavaTutorialDetailed examples of subset sum problems

Detailed examples of subset sum problems

Jul 03, 2017 am 11:03 AM
dynamic programmingSubsetquestion

Note: Because the study of "subsets and problems" is not in-depth enough, this article may have unclear descriptions or errors in explaining the dynamic programming recursion formula. If you find any, I hope you can Don’t hesitate to teach me.

The subset sum problem can be described as follows: Given n positive integers W=(w1, w2, …, wn) and the positive integer M are required to find such A subsetI⊆{1, 2, 3, ..., n},so that∑wi=M,i∈I[1] . Take an example to give a popular explanation of the subset sum problem: Set W=(1, 2, 3, 4, 5), given a positive integer M =5, whether there is a subset I of W such that the subset ## The sum of the elements in #I is equal to M. In this example, there is obviously a subset I=(2, 3).

Problem definition: Positive integer set

S=(w1, w2, w3, …, wn), given a positive Integer W, i in s[i, j] represents # A subset of ##S, j represents the sum of the subset i. If the sum of elements S of a certain set i#j=M, That is, the problem has a solution. Example: S=(7, 34, 4, 12, 5, 3)

W=6, whether there is a subset of S, the sum of its elements is equal to W. There are also many solutions to this problem. In this article, we use the idea of ​​dynamic programming to solve it, so we need to derive a recursive formula. We continuously divide the set S

into small sets. This is the first step of

dynamic programming: defining the sub-problem . The smallest set of set S is the empty set. Of course, the empty set does not exist and the sum of its elements is equal to W. Of course, if## In the case of #j=0, the empty set is eligible.

The columns of this table represent the sum of the elements in the set. It can only reach the element W at most. It is of course meaningless if it is greater than W. . As long as 1 appears in the j=6 column, the solution to the problem is obtained. The row represents a subset composed of the first i (including i) elements (this sentence may be a bit doubtful, isn’t this Can’t scan everything? Read on). i=0 represents the empty set.

When we define j=6, the empty set situation is true. Then when j=0, this is true for any subset sum (the empty set is their subset). So the form continues to populate as shown below.

These are actually the third step of dynamic programming: defining the initial state. The second step of state planning is to define state transition rules, that is, the recursive relationship between states.

The i in s[i, j] represents the first i Subset (includes i). In fact, we divide it into two parts from here:

 1) Excluding the first i# of the ith element ## subset, that is, s[i - 1, j]

  2) Includes the

i The first i subset of elements. It is easier to understand the
1) situation. The sum of the first i - 1 set elements is equal to j, then the sum of the subset elements of the first i set elements is equal to j.

What is difficult to understand is the 2) situation. One thing that can be made clear about the second situation is that the i in s[i, X] is certain, and the key is j, jHow to define it at this time? Using "Special value method" in mathematics, take the example set(3, 34, 9), whether there is a sum of elements of a given subset equal to 37, at this time i=2 (subset is (3, 34)), j = 37, at this time Includes the first i subset of the i elementThis kind In the case, s[2, 37] => s[2, 37 - 34] = s[2, 3], subset (3 , 34) Of course there is a subset whose sum of elements is equal to 3. Then if j = 36, s[2, 36] => s[2, 36 - 34] = s[2, 2], the subset (3, 34) obviously does not exist and the sum of its subset elements is equal to 2. What about j = 1, s[2, 1] => s[2, 1 - 34] = s[2, -32]j - wi , at this time s[2, 1] => s[2 - 1, 1] = s[1, 1], subset (3) obviously does not exist and the sum of its subset elements is equal to 1.

In summary, the recursive formula is as follows:

Before implementing this algorithm in code, first fill in the above through the recursive formula matrix.

 ①i = 1, The subset at this time is (7), j = 1, j ∉ (∅), selection situation2) => s[0, 1] || s[1, -6] (i = 0 represents the empty set). Obviously s[1, 1] = 0.

 ②i = 1, The subset at this time is (7), j = 2, j ∉ (∅), selection situation2) => s[0, 2] || s[1, -5]i = 0 represents the empty set). Obviously s[1, 2] = 0.

 ……

 ⑥i = 1, at this time the subset is (7), j = 6, j ∉ (∅), selection situation 2) => s[0, 6] || s[1 , -1] (i = 0 represents the empty set). Obviously s[1, 6] = 0.

The final filling is as shown below:

Continue to fill in the final One line:  

 ①i = 6, The subset at this time is(7, 34, 4, 12, 5, 3),j = 1, j ∉ (7, 34, 4, 12, 5), selection situation 2) => ; s[5, 1] ​​|| s[6, -2] (i = 0 represents the empty set). Obviously s[6, 1] = 0.

 ②i = 6, The subset at this time is (7, 34, 4, 12, 5, 3), j = 2, j ∉ (7, 34, 4, 12, 5), selection situation 2) => s[5, 1] || s[6, -1] (i = 0 represents the empty set). Obviously s[6, 2] = 0.

 ③i = 6, The subset at this time is (7, 34, 4, 12, 5, 3), j = 3, j ∉ (7, 34, 4, 12, 5), selection situation 2) => s[5, 1] ​​| | s[6, 0]. Obviously s[6, 3] = 1.

 ...

 ⑥i = 6, The subset at this time is(7, 34, 4, 12, 5, 3), j = 6, j ∉ (7, 34, 4, 12, 5), selection situation2) => s[5, 6] || s[6, 3]. Obviously s[6, 6] = 1.

  Java

##
 1 package com.algorithm.dynamicprogramming; 2  3 import java.util.Arrays; 4  5 /** 6  * 子集和问题 7  * Created by yulinfeng on 7/2/17. 8  */ 9 public class SubsetSumProblem {10 11     public static void main(String[] srgs) {12         int[] sets = {7, 34, 4, 12, 5, 3};13         int sum = 87;14         boolean isExistSubSet = subsetSumProblem(sets, sum);15         System.out.println("集合" + Arrays.toString(sets) + "是否存在子集的和等于" + sum + ":" + isExistSubSet);16     }17 18     private static boolean subsetSumProblem(int[] sets, int sum) {19         int row = sets.length + 1;20         int col = sum + 1;21         int[][] solutionMatrix = new int[row][col];22         solutionMatrix[0][0] = 1;23 24         /**25          *    0 1 2 3 4 5 626          * 0 |1|0|0|0|0|0|0|27          * 1 |x|x|x|x|x|x|x|28          * 2 |x|x|x|x|x|x|x|29          * 3 |x|x|x|x|x|x|x|30          * 3 |x|x|x|x|x|x|x|31          * 4 |x|x|x|x|x|x|x|32          * 5 |x|x|x|x|x|x|x|33          * 6 |x|x|x|x|x|x|x|34          */35         for (int i = 1; i = 0 && solutionMatrix[i][j - sets[i - 1]] == 1) {59                     solutionMatrix[i][j] = solutionMatrix[i][j - sets[i - 1]];60                 } else {61                     solutionMatrix[i][j] = 0;62                 }63 64                 if (j == col - 1 && solutionMatrix[i][j] == 1) {65                     return true;66                 }67             }68         }69 70         return false;71     }72 }

  Python3

 1 def subset_sum_problem(sets, sum): 2     row = len(sets) + 1 3     col = sum + 1 4     solutionMatrix = [[0 for col in range(col)] for row in range(row)] 5     solutionMatrix[0][0] = 1 6     for i in range(1, col): 7         solutionMatrix[0][i] = 0 8  9     for j in range(1, row):10         solutionMatrix[j][0] = 111         for k in range(1, col):12             solutionMatrix[j][k] = solutionMatrix[j - 1][k]13             if solutionMatrix[j][k] == 1:14                 solutionMatrix[j][k] = solutionMatrix[j][k]15             elif (k - sets[j - 1] >= 0) and (solutionMatrix[j][k - sets[j - 1]] == 1):16                 solutionMatrix[j][k] = solutionMatrix[j][k - sets[j - 1]]17             else:18                 solutionMatrix[j][k] = 019             if k == col - 1 and solutionMatrix[j][k] == 1:20                 return True21 22     return False23 24 sets = [7, 34, 4, 12, 5, 3]25 num = 626 is_exist = subset_sum_problem(sets, num)27 print(is_exist)


The above is the detailed content of Detailed examples of subset sum problems. For more information, please follow other related articles on the PHP Chinese website!

Statement
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
How does IntelliJ IDEA identify the port number of a Spring Boot project without outputting a log?How does IntelliJ IDEA identify the port number of a Spring Boot project without outputting a log?Apr 19, 2025 pm 11:45 PM

Start Spring using IntelliJIDEAUltimate version...

How to elegantly obtain entity class variable names to build database query conditions?How to elegantly obtain entity class variable names to build database query conditions?Apr 19, 2025 pm 11:42 PM

When using MyBatis-Plus or other ORM frameworks for database operations, it is often necessary to construct query conditions based on the attribute name of the entity class. If you manually every time...

How to use the Redis cache solution to efficiently realize the requirements of product ranking list?How to use the Redis cache solution to efficiently realize the requirements of product ranking list?Apr 19, 2025 pm 11:36 PM

How does the Redis caching solution realize the requirements of product ranking list? During the development process, we often need to deal with the requirements of rankings, such as displaying a...

How to safely convert Java objects to arrays?How to safely convert Java objects to arrays?Apr 19, 2025 pm 11:33 PM

Conversion of Java Objects and Arrays: In-depth discussion of the risks and correct methods of cast type conversion Many Java beginners will encounter the conversion of an object into an array...

How do I convert names to numbers to implement sorting and maintain consistency in groups?How do I convert names to numbers to implement sorting and maintain consistency in groups?Apr 19, 2025 pm 11:30 PM

Solutions to convert names to numbers to implement sorting In many application scenarios, users may need to sort in groups, especially in one...

E-commerce platform SKU and SPU database design: How to take into account both user-defined attributes and attributeless products?E-commerce platform SKU and SPU database design: How to take into account both user-defined attributes and attributeless products?Apr 19, 2025 pm 11:27 PM

Detailed explanation of the design of SKU and SPU tables on e-commerce platforms This article will discuss the database design issues of SKU and SPU in e-commerce platforms, especially how to deal with user-defined sales...

How to set the default run configuration list of SpringBoot projects in Idea for team members to share?How to set the default run configuration list of SpringBoot projects in Idea for team members to share?Apr 19, 2025 pm 11:24 PM

How to set the SpringBoot project default run configuration list in Idea using IntelliJ...

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Tools

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

Powerful PHP integrated development environment

mPDF

mPDF

mPDF is a PHP library that can generate PDF files from UTF-8 encoded HTML. The original author, Ian Back, wrote mPDF to output PDF files "on the fly" from his website and handle different languages. It is slower than original scripts like HTML2FPDF and produces larger files when using Unicode fonts, but supports CSS styles etc. and has a lot of enhancements. Supports almost all languages, including RTL (Arabic and Hebrew) and CJK (Chinese, Japanese and Korean). Supports nested block-level elements (such as P, DIV),

Atom editor mac version download

Atom editor mac version download

The most popular open source editor

VSCode Windows 64-bit Download

VSCode Windows 64-bit Download

A free and powerful IDE editor launched by Microsoft

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment