51nod-正整数分组问题(基础方程DP-01背包)
2024-10-09 20:51:15
正整数分组
将一堆正整数分为2组,要求2组的和相差最小。
例如:1 2 3 4 5,将1 2 4分为1组,3 5分为1组,两组和相差1,是所有方案中相差最少的。
思路:
这题的实质其实也是0-1背包问题,但是要想理解到这一步,或者说想要用0-1背包来解决这个问题,就必须将问题抽象化到一定的程度才可以。
一列数,无序,给他分成两半,要想实现两半的和的差最小,就是恨不得恰好均分了。那么我们按照0-1背包的那种”一维式“的思维来想,这个问题就别转化成了从第一个数开始到最后一个数,选出一些数,使他们的和最大程度的接近所有数的和的一半,将这些数作为一组,那么剩下的数就是另一组了。
按照之前0-1背包的思路,这题就迎刃而解了。
#include <cmath>
#define INF 65535
using namespace std; int n;
int f[];
int sum;
int num[]; int main()
{
int other;
while(~scanf("%d",&n))
{
sum = ;
for(int i = ;i <= n;i++){
scanf("%d",&num[i]);
sum += num[i];
}
memset(f,,sizeof(f));
for(int i = ;i <= n;i++)
for(int j = sum/;j >= num[i];j--)
f[j] = max(f[j],f[j-num[i]]+num[i]);
other = sum - f[sum/];
printf("%d\n",abs(other-f[sum/]));
}
return ;
}
最新文章
- PHP通过XML报文格式的POST请求方式,与第三方接口交互(发送xml,获取XML,并解析xml步骤)
- ubuntu 13.10 svn工具 rabbitvcs 安装
- MySQL模拟:线上误update的恢复
- hdu敌兵布阵
- HTTP和FTP的区别
- SystemServer相关
- seajs第二节,seajs各模块依赖关系
- TFS的使用
- C++ 用libcurl库进行http通讯网络编程[转]
- XSS【跨站脚本攻击】
- poj 3487 稳定婚姻
- Android项目--浅析系统通讯录中的那些方法
- Java将List/JavaBean转成Json
- [补档][Tyvj 1728]普通平衡树
- eclipse自定义代码模板
- JavaBean初识
- 根据cid获取哔哩哔哩弹幕
- 595. Big Countries --- SQL related from leetcode
- Nginx 403 forbidden多种原因及故障模拟重现
- JAVA编程:字符串转为数字求和
热门文章
- Android四大组件——Activity
- intellij安装Scala及Python插件
- 【解决】WordPress FTP连接服务器时出错,请检查设置,WordPress需要访问您网页服务器的权限
- JSON 格式化为易读格式的字符串
- C# DBNULL与NULL之间的区别【转】
- php的mq客户端获取队列方法改造
- Android开发手记(7) 按钮类控件的使用
- 如何给report自定义page number
- Linux ulimit 系统资源控制
- 真机测试,Xcode报错:process launch failed: Security