这里;http://acm.hdu.edu.cn/showproblem.php?pid=1059

题意是有价值分别为1,2,3,4,5,6的商品各若干个,给出每种商品的数量,问是否能够分成价值相等的两份.

联想到多重背包,稍微用二进制优化一下。(最近身体不适,压力山大啊)

 #include<iostream>
#include<cstring>
#include<cstdio>
#define inf 70000
using namespace std;
int dp[inf];
int sum;
void pack(int price)
{
for(int i = sum; i >= price; i--) dp[i] = max(dp[i], dp[i - price] + price);
}
int main()
{
int a[],i,q=,j;
while (~scanf("%d %d %d %d %d %d",&a[],&a[],&a[],&a[],&a[],&a[]))
{
if (a[]==&&a[]==&&a[]==&&a[]==&&a[]==&&a[]==)
break;
memset(dp,-inf,sizeof(dp));
dp[]=;
printf("Collection #%d:\n",q++);
sum=;
for (i=;i<=;i++)
sum+=a[i]*i;
if (sum%!=)
{
printf("Can't be divided.\n\n");
continue;
}
sum/=;
for (i=;i<=;i++)
{
if (i*a[i]>=sum)
{
for (j=i;j<=sum;j++)
dp[j]=max(dp[j],dp[j-i]+i);
}
else
{
int k = ;
while(k < a[i])
{
pack(k * i);
a[i] -= k;
k += k;
}
pack(a[i] * i);
}
}
if (dp[sum]==sum)
printf("Can be divided.\n\n");
else
printf("Can't be divided.\n\n");
}
return ;
}

最新文章

  1. Oracle数据库的备份方法
  2. Asp.net_完美设置页面最小宽度(兼容ie)
  3. Python开发入门与实战9-基于vs的集成开发环境
  4. Why we need template on Django ?
  5. PLSQL 的简单命令之五
  6. jquery on off 方法
  7. Win7+xp命令行 一键修改IP、DNS
  8. android手机操作SD的使用方法
  9. HTTP,TCP,Socket
  10. 利用DreamweaverCS5制作一个含有动态标题的教程
  11. javascript--时钟
  12. Oracle存储过程Procedure语法及案例
  13. Canvas的quadraticCurveTo 和 bezierCurveTo 画曲线 方法细说
  14. Code Blocks 使用 VC2013编译HelloWord
  15. 水流(water)
  16. Hbase rowkey设计+布隆过滤器+STORE FILE &amp; HFILE结构
  17. tmux入门
  18. Linux安全之SYN攻击原理及其应对措施
  19. c#中partial 作用
  20. tf.nn.embedding_lookup函数的用法

热门文章

  1. &#39;Could not find first log file name in binary log index file&#39;的解决办法
  2. apache启动报错(98)Address already in use: make_sock: could not bind to address [::]:80
  3. 目前为止最全的微信小程序项目实例
  4. sqlite 时间戳转时间
  5. 昆虫之膜翅目(Hymenoptera)
  6. Eclipse 合并GIT分支
  7. Pandas之数据结构
  8. js setInterval参数设置
  9. Error:stray &#39;\243&#39; in program
  10. cisco 交换机通过console 导入 IOS