http://poj.org/problem?id=1014

最简单之多重背包

 #include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define MAX(a,b) (a > b ? a : b)
#define MIN(a,b) (a < b ? a : b)
#define mem0(a) memset(a,0,sizeof(a)) typedef long long LL;
const double eps = 1e-;
const int MAXN = ;
const int MAXM = ; int num[], DP[], F; void ZeroOnePack(int v)
{
for(int i=F;i>=v;i--)
{
DP[i] = max(DP[i], DP[i-v]+v);
}
} void CompletePack(int v)
{
for(int i=v;i<=F;i++)
{
DP[i] = max(DP[i], DP[i-v]+v);
}
} int ComplexPack()
{
for(int i=;i<=;i++)
{
if(num[i]*i >= F) CompletePack(i);
else
{
int k = ;
while(k <= num[i])
{
ZeroOnePack(k*i);
num[i] -= k;
k *= ;
}
ZeroOnePack(num[i]*i);
}
}
return DP[F];
} int main()
{
int T=;
while(scanf("%d%d%d%d%d%d", &num[],&num[],&num[],&num[],&num[],&num[]))
{
if(!(num[]||num[]||num[]||num[]||num[]||num[])) break;
F = ; mem0(DP);
for(int i=;i<=;i++) F += num[i]*i;
printf("Collection #%d:\n", ++T);
if(F & ) {printf("Can't be divided.\n\n"); continue;}
F /= ;
printf("%s\n\n", ComplexPack()==F?"Can be divided.":"Can't be divided.");
}
return ;
}

最新文章

  1. java时间
  2. 【bzoj3450】Tyvj1952 Easy
  3. 浅谈java抽象类和接口
  4. 基础复习 关于JS
  5. 【C】 03 - 数据类型
  6. The Python web services developer: XML-RPC for Python
  7. Lucene.net常见功能实现知识汇总
  8. jquery 左边分类+插件
  9. Windows Embedded CE 6.0 下载地址和序列号
  10. Red and Black---POJ - 1979
  11. 三种方法实现CSS三栏布局
  12. SQL 约束 索引
  13. python函数解释
  14. php编程 之 php基础三
  15. 2019.01.23 hdu1693 Eat the Trees(轮廓线dp)
  16. jQuery ajax请求错误返回status 0和错误error的问题
  17. Html5多媒体相关的API---video
  18. MySQL知识小结
  19. let与var区别
  20. 判断一个字符是否为数字的两种方法(C/C++)

热门文章

  1. JavaScript——new Date().getMonth()
  2. (转载) jQuery 页面加载初始化的方法有3种
  3. volley(2) 参数code : or_barcode, pr_ismsd:false , method:GET
  4. kdtree备份
  5. (转)Mac OS X写了个rm时将文件放入回收站的小工具
  6. ecms_任意页面调用单独的栏目
  7. type tips
  8. InnoDB 引擎独立表空间 innodb_file_per_table
  9. 嵌入式 H264—MP4格式及在MP4文件中提取H264的SPS、PPS及码流
  10. android学习——MeasureSpec介绍及使用