9.动态规划(2)——子集和问题

注:因为对“子集和问题”的学习不够深入,所以本文在讲解动态规划递推公式中可能存在叙述不清,或者错误的地方,如有发现望能不吝赐教。

  子集和问题可描述如下:给定n个正整数W=(w1, w2, …, wn)和正整数M,要求寻找这样一个子集I⊆{1, 2, 3, ..., n},使得∑wi=M,i∈I[1]。举个例子对子集和问题做一个通俗的解释:集合W=(1, 2, 3, 4, 5),给定一个正整数M=5,是否存在W的一个子集I,使得子集I中的元素相加等于M,这个例子显然存在子集I=(2, 3)。

  问题定义:正整数集合S=(w1, w2, w3, …,wn),给定正整数W,s[i, j]中的i表示S的一个子集,j表示子集i的和。如果S的某个集合i元素之和j=M,即问题有解。

  举例:S=(7, 34, 4, 12, 5, 3),W=6,是否存在S的一个子集,它的元素之和等于W。

  这个问题同样有多种解法,在本文中利用动态规划的思想进行求解,那么就需要推导出一个递推公式。我们将集合S不断的划分为小的集合,这就是动态规划的第一步:定义子问题。集合S最小的集合就是空集,空集当然不存在它的元素之和等于W,当然若j=0的情况下空集是符合条件的。

  这个表格的列代表的是集合中的元素之和,最多只到达元素W,大于W当然没意义了。只要在j=6列中出现1,即得到问题的解。行表示前i个(包括i)元素组成的子集(这句话可能会有点疑问,这样岂不是扫描不到所有情况吗?接着往下看)。i=0表示为空集。

  我们定义了j=6时,空集情况为true。那么当j=0时,这样对任意子集和都成立(空集是它们的子集)。所以表格继续填充如下图所示。

  这些实际上是动态规划的第三步:定义初始状态。状态规划第二步则是定义状态转移规则,即状态之间的递推关系。

  s[i, j]中的i表示的是前i个子集(包括i)。实际上我们从这里进行划分为两部分:

    1)不包括第i个元素的前i个子集,即s[i - 1, j];

    2)包括第i个元素的前i个子集。   对于第1)种情况较易理解,前i - 1个集合元素之和等于j,那么前i个集合元素就存在子集元素之和等于j。

  难于理解的是第2)种情况。对于第二种情况能明确一点就是s[i, X]中的i是确定的,关键是j,j此时如何定义?利用数学中的“特值法”,举例集合(3, 34, 9),是否存在给定子集的元素之和等于37,此时i=2(子集为(3, 34)),j = 37,此时“包括第i个元素的前i个子集”这种情况下,s[2, 37] => s[2, 37 - 34] = s[2, 3],子集(3, 34)当然存在它的子集元素之和等于3。那如果j = 36,s[2, 36] => s[2, 36 - 34] = s[2, 2],子集(3, 34)显然不存在它的子集元素之和等于2。那j = 1呢,s[2, 1] => s[2, 1 - 34] = s[2, -32],j - wi < 0,此时s[2, 1] => s[2 - 1, 1] = s[1, 1],子集(3)显然不存在它的子集元素之和等于1。

  综上,递推式如下所示:

  在用代码实现这个算法前,先通过递推公式填写上面的矩阵。

  ①i = 1, 此时子集为(7),j = 1,j ∉ (∅),选择情况2) => s[0, 1] || s[1, -6](i = 0表示空集)。显然s[1, 1] = 0。

  ②i = 1,此时子集为(7),j = 2,j ∉ (∅),选择情况2) => s[0, 2] || s[1, -5](i = 0表示空集)。显然s[1, 2] = 0。

  ……

  ⑥i = 1,此时子集为(7),j = 6,j ∉ (∅),选择情况2) => s[0, 6] || s[1, -1](i = 0表示空集)。显然s[1, 6] = 0。

  最后填充为如下图所示:

  继续填充最后一行:  

  ①i = 6, 此时子集为(7, 34, 4, 12, 5, 3),j = 1,j ∉ (7, 34, 4, 12, 5),选择情况2) => s[5, 1] || s[6, -2](i = 0表示空集)。显然s[6, 1] = 0。

  ②i = 6, 此时子集为(7, 34, 4, 12, 5, 3),j = 2,j ∉ (7, 34, 4, 12, 5),选择情况2) => s[5, 1] || s[6, -1](i = 0表示空集)。显然s[6, 2] = 0。

  ③i = 6, 此时子集为(7, 34, 4, 12, 5, 3),j = 3,j ∉ (7, 34, 4, 12, 5),选择情况2) => s[5, 1] || s[6, 0]。显然s[6, 3] = 1。

  ...

  ⑥i = 6, 此时子集为(7, 34, 4, 12, 5, 3), j = 6, j ∉ (7, 34, 4, 12, 5),选择情况2) => s[5, 6] || s[6, 3]。显然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 6
26          * 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 < col; i++) {
36             solutionMatrix[0][i] = 0;
37         }
38         /**
39          * 初始状态
40          *    0 1 2 3 4 5 6
41          * 0 |1|0|0|0|0|0|0|
42          * 1 |1|0|x|x|x|x|x|
43          * 2 |x|x|x|x|x|x|x|
44          * 3 |x|x|x|x|x|x|x|
45          * 3 |x|x|x|x|x|x|x|
46          * 4 |x|x|x|x|x|x|x|
47          * 5 |x|x|x|x|x|x|x|
48          * 6 |1|0|0|x|x|x|x|
49          * [i][0] = 1,按行填充
50          */
51         for (int i = 1; i < row; i++) {
52             solutionMatrix[i][0] = 1;
53             for (int j = 1; j < col; j++) {
54                 solutionMatrix[i][j] = solutionMatrix[i - 1][j];
55 
56                 if (solutionMatrix[i][j] == 1) {
57                     solutionMatrix[i][j] = solutionMatrix[i][j];
58                 } else if ( j - sets[i - 1] >= 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 c in range(col)] for r 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] = 1
11         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] = 0
19             if k == col - 1 and solutionMatrix[j][k] == 1:
20                 return True
21 
22     return False
23 
24 sets = [7, 34, 4, 12, 5, 3]
25 num = 6
26 is_exist = subset_sum_problem(sets, num)
27 print(is_exist)

[1]李肯立, 李庆华, 张红君. 子集和问题的改进算法[J]. 计算机科学, 2003, 30(11):16-17.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Bingo的深度学习杂货店

最小方差划分

给一个数组,求一个k值,使得前k个数的方差 + 后面n-k个数的方差最小 解题思路: 如果不考虑方差的概念,这题可以简化为 “给一个数组,求一个k值,使得前k个...

53530
来自专栏偏前端工程师的驿站

代数几何:点,线,抛物线,圆,球,弧度和角度

一, 笛卡尔坐标系                         ? 笛卡尔坐标系是数学中的坐标系,而计算机中则采用屏幕坐标系统. ? 而三维坐标系则没有一个...

26580
来自专栏小樱的经验随笔

容斥原理

容斥原理 对容斥原理的描述 容斥原理是一种重要的组合数学方法,可以让你求解任意大小的集合,或者计算复合事件的概率。 描述 容斥原理可以描述如下: 要计算几个...

47170
来自专栏magicsoar

动态规划(dynamic programming)

动态规划的基本思想 动态规划的基本思想在于发现和定义问题中的子问题,这里子问题可也以叫做状态;以及一个子问题到下一个子问题之间 是如何转化的 也就是状态转移方程...

34850
来自专栏杂七杂八

matlab中的函数介绍(max,min,unidrnd,norm)

遇到不知道的函数时,可以使用help 函数名来查看帮助 1 求矩阵A的最大值的函数有3种调用格式,分别是: max(A):返回一个行向量,向量的第i个元...

40950
来自专栏fangyangcoder

leetcode(三)

给定一个二维的矩阵(矩阵的数全由1和0组成),任意反转矩阵的每一行和每一列(0反转成1,1反转成0),求出最大矩阵分数,矩阵分数的求法是矩阵每一行代表二进制数,...

15330
来自专栏mathor

matlab—方程式求根

23540
来自专栏我和未来有约会

[Silverlight动画]转向行为 - 2D向量

转向行为已经被各种语言实现过多次了,其最底层是用向量来描述的(也是最常见的实现方式)。 概括的看,一个向量由两部分组成:一个方向和一个大小。比如,一个运动中对象...

22260
来自专栏专知

【干货】深入理解自编码器(附代码实现)

【导读】自编码器可以认为是一种数据压缩算法,或特征提取算法。本文作者Nathan Hubens 介绍了autoencoders的基本体系结构。首先介绍了编码器和...

1.6K70
来自专栏深度学习之tensorflow实战篇

Python中map函数

python中的map()函数 map(function, iterable, ...) 1.对可迭代函数'iterable'中的每一个元素应用‘functi...

37440

扫码关注云+社区

领取腾讯云代金券