POJ1014Dividing(DP)

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

最简单之多重背包

POJ1014Dividing(DP)

 #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 ;
}
上一篇:Linux的五个查找命令find,locate,whereis,which,type


下一篇:android网络编程之HttpUrlConnection的讲解--实现文件的断点上传