算法二之子集和数问题

什么是子集和数问题?

问题分析,简单的说就是有n 个数在这N个数中选取若干个数使得这几个数的和为M。

解决问题的途径;使用回溯法。

最后形成二叉树

左边是有这个数,右儿子是没有这个数。

使用回溯法,一个一个的进行计算,时间太长。

使用一定的条件,使得时间减短。

前提是对所有的数字进行非降序排序,然后在进行下面的操作。

限界函数,将有可能产生解的集合进行缩小。有的不可能产生可行解的直接进行排除。

∑W(i)X(i)+∑W(i)>=M

∑W(i)X(i)+W(k+1)>M

如果加入一个数k,如果k-1个数的和小于M,加上K小于M但是加上k的下一个数后大于M,那么数k也不用进行计算,直接排除。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏java一日一条

8张图理解Java

HashCode被设计用来提高性能。equals()方法与hashCode()方法的区别在于:

761
来自专栏精讲JAVA

8 张图理解 Java

一图胜千言,下面图解均来自Program Creek 网站的Java教程,目前它们拥有最多的票选。如果图解没有阐明问题,那么你可以借助它的标题来一窥究竟。

931
来自专栏祥子的故事

Python编程快速上手 让繁琐工作自动化 | 第三章 :实践项目

3116
来自专栏Web项目聚集地

8张图理解Java

一图胜千言,下面涉及的图解均来自Program Creek 网站的Java教程,目前它们拥有最多的票选。如果图解没有阐明问题,那么你可以借助它的标题来一窥究竟。

1061
来自专栏闻道于事

Java异常处理中的恢复模型

2814
来自专栏mathor

LeetCode329. 矩阵中的最长递增路径

 dfs,主函数中枚举起点,然后dfs函数中枚举四个方向进行移动,但是光dfs还不够,因为我们发现存在很多冗余,所以这是一道dfs+dp的问题,resul...

1561
来自专栏大闲人柴毛毛

Redis源码分析(三)——Redis数据结构-字典

1. 数据结构 ? 1.1 哈希表 typedef struct dictht{ dictEntry **table; unsigned long s...

3065
来自专栏生信宝典

R语言学习 - 韦恩图

韦恩图 韦恩图是用来反映不同集合之间的交集和并集情况的展示图。一般用于展示2-5个集合之间的交并关系。集合数目更多时,将会比较难分辨,更多集合的展示方式一般使用...

3447
来自专栏java初学

海量数据处理

49514
来自专栏用户画像

7.7.4 置换选择排序(生成初始归并段)

7.7.3讨论了如何使用m路归并来减少磁盘访问次数。从第7.7.2的讨论可知,减少初始归并段个数r也可以减少归并趟数S。若总的记录个数为n,每个归并段的长度为L...

1422

扫码关注云+社区

领取腾讯云代金券