1,题意:2n个正整数,分成两组n,使其和最接近.
2,思路:
动态规划: isOK[i][v]表示是否可以找打i个数,使得他们之和等于v.
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int m = 0xffff;
bool isOK[100][m];
void HalfSum(int data[], int N)
{
memset(isOK, 0, sizeof(isOK));
isOK[0][0] = true;
int sum = 0;
int n = N/2;
for (int i = 0; i < N; ++i)
sum += data[i];
for (int k = 1; k < N; ++k)
{
for (int i = 1; i <= min(k, n); ++i)
{
for (int v = 1; v <= (sum / 2); ++v)
if ((v >= data[k]) && isOK[i - 1][v - data[k]])
isOK[i][v] = true;
}
}
int ret = sum / 2;
while (!isOK[n][ret])
--ret;
cout << ret << endl;
}
int main()
{
int data[] = {1, 5, 7, 8, 9, 6, 3, 11, 20, 17};
HalfSum(data, sizeof(data) / sizeof(data[0]));
return 0;
}
分享到:
相关推荐
struts2.18 all zip
2.18版联想G460 BIOS更新程序,更新之后让老机器不限制网卡品牌,只要接口一致即可。
linux中glibc-2.18.tar.gz解压使用 linux中glibc-2.18.tar.gz解压使用
struts 2.18 jar包里面包含Myeclipse开发所需要的7个jar
ProxifierMac2.18 含注册码,请详细看压缩包描述,SN注册码说明
rufus-2.18.zip
Git_2.18-win64banben Git_2.18-win64banben Git_2.18-win64banben
Goahead 2.18源码分析,为使用Goahead中遇到问题的提供帮助
pandoc-2.18-windows-x86_64 Windows zip压缩包! Pandoc是标记语言转换工具,可实现不同标记语言间的格式转换,堪称该领域中的“瑞士军刀”。 Pandoc使用Haskell语言编写,以命令行形式实现与用户的交互,可支持...
在git官网下载一个git需要很长时间,所以把它上传到csdn里,方便有需要的下载。
解决 /lib64/libc.so.6: version `GLIBC_2.18' not found 问题
struts2.18框架的源码 struts2.18框架的源码
全智能版2.18软件安装包
window 2.18版git安装包,下载后直接解压里面有安装包
Windows环境下的Pandoc2.18版本,适用Typora Windows环境下的Pandoc2.18版本,适用Typora Windows环境下的Pandoc2.18版本,适用Typora Windows环境下的Pandoc2.18版本,适用Typora
支持linux(suse)系统的glibc.rpm包,64位
学习struts2.18 很完整的例子 含文件上传 及DWR 等 DEMO含JAR包
Git-2.18-64bit,Windows版本,程序员代码管理利器,温情提供下载
QX模块 v2.18更新版 QQ强红包防撤回利器.zip含下载地址可存云盘
整合struts2.18+spring3.0.2+hibernate3.5.1,全部都是目前最新版本。手动添加的jar包,没有任何冗余。数据库是mysql5.0,有一张表“Test”,里面有两个字段“testid”、“testvalue”。