一、前言

这是神州南部的SZ大学某门水课的大作业。如果你也不幸进了这所大学，也跟我一样报了LH老师的课，我的这份作业也许能帮你节省不少时间。

二、问题

我拿到的NP问题是Partion Problem，这是一个最简单的NP-Hard问题。其问题大概是这样的：

给定一个含有个元素的集合：

问是否存在集合的一个划分：，使得的元素之和等于的元素和。例如，给定下列集和：

我们可以把上面集合划分成和，这两个集合的元素和都为27。对于这个问题，如果穷举所有可能性的话，其时间复杂度是，且这个问题的复杂主要受集合的长度和集合中元素的大小的影响。如果集合长度短或者是集合中的最大元素比较小，都可以找到一个多项式时间算法去解决这个问题。

三、解法

我上网收到了两篇论文：

image.png
image.png

一个是用动态规划+回溯法来求解，另一个是用变领域的遗传算法来求解。下面我简单介绍一下。

动态规划+回溯法

设集合的长度为 ，集合中最长的元素为 ，当比值比较大时，说明这个集合比较稠密，这时我们偏向于用动态规划求解划分问题；而当这个比值比较小时，说明集合比较稀疏，这时我们倾向于用回溯方法解决划分问题，因为如果用动态规划去解决稀疏集合的话，就会浪费大量的内存空间。

基于上面的分析，我们最终结合动态规划和回溯法这两种算法。其主要思想是先把集合分成两个部分，一部分是稀疏的集合，另一部分是稠密的集合。对于稀疏的集合，就用回溯法解决；对于稠密的集合，就用动态规划进行求解。这种策略很好融合了动态规划与回溯法的优点，使得算法更加快速高效。其具体算法如下：

image.png

并行可对回溯法进行。

变领域遗传算法

这里并不仔细介绍遗传算法和变领域算法，不了解的自行百度了解一下。

image.png

• 染色体编码就用0-1数组，0表示元素不在集合中，1表示元素不在集合中。这样构造出来的一条染色体就表示该问题的一个可行解。（一条染色体只能表示原来集合的一个子集，但对染色体取反就能得到原来集合的另一个子集，且这两个集合就是原来集合的一个划分。）

代码和PPT

福利：https://github.com/WinddyAkoky/Number-Partition-Problem

友情提示：emmmm这份代码有点问题，就是dp_bs的并行时间比串行时间长。。。。尴尬。。。。不过LH那货肯定不看。。哈哈哈哈。。。如果你能把dp_bs的并行改好了，记得给我一个留言，我学习学习 -_-