Dynamic Programming | Set 18 (Partition problem)
Partition problem is to determine whether a given set can be partitioned into two subsets such that the sum of elements in both subsets is same.
Examples
arr[] = {1, 5, 11, 5}
Output: true
The array can be partitioned as {1, 5, 5} and {11}
arr[] = {1, 5, 3}
Output: false
The array cannot be partitioned into equal sum sets.
Following are the two main steps to solve this problem:
1) Calculate sum of the array. If sum is odd, there can not be two subsets with equal sum, so return false.
2) If sum of array elements is even, calculate sum/2 and find a subset of array with sum equal to sum/2.
The first step is simple. The second step is crucial, it can be solved either using recursion or Dynamic Programming.
http://www.geeksforgeeks.org/dynamic-programming-set-18-partition-problem/
Following are the two main steps to solve this problem:
解析为:
1 检查数组的总和是否是偶数,如果是基数就返回假
2 问题归结为在一个数组中寻找任意数组合的和等于一个数的问题(其中数组的数只能使用一次)。明白点说就是coin change问题(找零钱)
bool findPartiion (int arr[], int n)
{
int sum = 0;
for (int i = 0; i < n; i++)
{
sum += arr[i];
}
if (sum % 2) return false;
sum /= 2;
bool *A[2];
A[0] = new bool[sum+1];
A[1] = new bool[sum+1];
A[0][0] = true;
for (int i = 1; i <= sum; i++) A[0][i] = false;
bool idx = true;
A[1][0] = true;
for (int i = 0; i < n; i++)
{
for (int j = 1; j <= sum; j++)
{
A[idx][j] = A[!idx][j];
if (j >= arr[i] && !A[idx][j]) A[idx][j] = A[!idx][j-arr[i]];
}
if (A[idx][sum]) return true;
idx = !idx;
}
return false;
}
原网站的解法效率:
Time Complexity: O(sum*n)
Auxiliary Space: O(sum*n)
Please note that this solution will not be feasible for arrays with big sum.
对比:
1 本博客程序时间效率基本上是一样的,不过实际运行应该快点,找到了找零方案就马上返回了,不用循环结束。
2 空间效率使用了O(sum),数组大的话,就节省了大量空间。
分享到:
相关推荐
wanwan-coco-partition框架,极简框架用于测试spring框架是否可用
minitool-partition-wizard的11版本,目前应该到12了,这个11是我之前下载的版本,测试过可以完全使用,我用该工具主要是用来将window系统镜像到新的硬盘里面去,这个工具有个好处是不管新的磁盘是否比旧的磁盘容量...
用Java开发的面向MySQL的分表插件。 支持将业务对象表在每个数据库中按-partition-manager
DVD分区资料, 对DVD开发人员也许有一定的作用
mysql表分区的建立,索引的建立,原理说明,还有就是实例的演示
通过udev创建分区名链接
Allegro 产品包中 Allegro Partitioning Option PA3410 是一种用于 PCB 团队合 作设计的功能模块,它可将一块复杂 PCB 板分成多个简单的 PCB 板,通过团队合作设计,合并设计的方法,可以大大提升设计效率,缩短设计...
这是关于在linux下磁盘分区命令fdisk使用的图文详细教程。
涉及到软件测试的西门子数据集,应用较多,可以验证方法的准确性
脚本将尝试根据算法从$ partition中删除文件 将使用以下算法: 删除不在节点上运行任何进程(〜未登录)并且未被任何其他进程使用的用户的所有文件 删除任何进程未使用的所有文件 找出已经被删除但仍在进程中使用...
oracle-partition-handler
基于partition的连接算法
软件介绍: 这个是银灿官方发布的最新版U盘分区工具,版本号V2.0.0.3可以设置唯一分区(包括一般磁盘、安全磁盘、只读磁盘)多光盘分割:唯一光盘分割或者是多光盘分割。混合磁盘分区:光盘 安全磁盘/只读磁盘 一般...
该波束形成功率地图separte多个来源的分区 ...Partition_Map.m 分区给定的(标准化)波束形成功率地图和findes连接的区域。返回潜力清单 源位置与相关的波束形成能力和皮皮的阈值的数量一起 或者这些来源已经找到。
IM-Magic Partition Resizer Pro 是一款功能强大的硬盘磁盘无损分区软件,它能帮助你快速安全地调整硬盘分区的大小。譬如笔记本使用起来发现C盘空间快要满了,IM-Magic Partition Resizer 可以帮助您从其他分区调...
7-Data Partition Recovery 是由香港 SharpNight 开发的的一款功能强大、专业有效的分区恢复软件,并且为中文界面企业版本,即下即用。该软件界面简洁大方,使用操作方便,免费是用来设计恢复数据丢失,删除或损坏的...
一些bsp的文档,pdf格式。主要是Binary Space Partioning Trees and Polygon Removal in Real Time 3D Rendering这篇
非常好用的分区工具,可以不用重装系统直接分区,重启后生效。
→ partition-manager --log-level=debug \ --mariadb test_tools/fake_mariadb.sh \ add --noop --table tablename DEBUG:root:Auto_Increment column identified as id DEBUG:root:Partition range column ...
C#,动态规划的集合划分问题(DP Partition problem)算法与源代码 1 动态规划问题中的划分问题 动态规划问题中的划分问题是确定一个给定的集是否可以划分为两个子集,使得两个子集中的元素之和相同。 动态规划...