POJ 1014 Dividing(多重背包+二进制优化)

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

题意:
6个物品,每个物品都有其价值和数量,判断是否能价值平分。

思路:

多重背包。利用二进制来转化成0-1背包求解。

 #include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std; const int maxn = ;
int sum;
int a[];
int d[maxn];
int w[maxn]; int main()
{
//freopen("D:\\txt.txt", "r", stdin);
int kase = ;
while (scanf("%d", &a[]))
{
for (int i = ; i <= ; i++)
scanf("%d", &a[i]);
sum = ;
for (int i = ; i <= ; i++)
sum += i*a[i];
if (sum == ) break; printf("Collection #%d:\n", ++kase); if (sum % )
{
printf("Can't be divided.\n\n");
continue;
}
int count = ;
for (int i = ; i <= ; i++)
{
int m = a[i];
int k = ;
while (k < m)
{
w[count++] = k*i;
m -= k;
k *= ;
}
w[count++] = m*i;
}
sum = sum / ;
memset(d, , sizeof(d));
for (int i = ; i < count; i++)
{
for (int j = sum; j >= w[i]; j--)
d[j] = max(d[j], d[j - w[i]] + w[i]);
}
if (d[sum]==sum)
printf("Can be divided.\n\n");
else
printf("Can't be divided.\n\n");
}
}
上一篇:HDOJ(HDU).1059 Dividing(DP 多重背包+二进制优化)


下一篇:tool list