poj 1014 Dividing （多重背包）
题目大意：有6种价值的大理石（为1~6）， 先给出每种价值的大理石若干， 求能不能将它们平分。
思路：背包9讲中的模板套着打就ok了， dp[j]表示重量为j时的价值， 这里重量等于价值。
这题和上一道题很像（.........）， 也可以用f[j]记录重量为j时是否出现过。
code：
#include <stdio.h>
#include <string.h>
int sum = 0, c[12], dp[20002*6];
void zero_one(int weight, int value)
{
int j = 0;
for(j = sum; j>=weight; j--)
dp[j] = dp[j]>dp[j-weight]+value? dp[j]:dp[j-weight]+value;
}
int main()
{
int i = 0, j = 0, k = 0, count = 0;
while(1)
{
sum = 0;
for(i = 1; i<=6; i++)
{
scanf("%d", &c[i]);
sum += i*c[i];
}
if(!sum)
break;
printf("Collection #%d:\n",++count);
if(sum%2 == 1)
printf("Can't be divided.\n");
else
{
sum /= 2;
memset(dp, 0, sizeof(dp));
for(i = 1; i<=6; i++)
{
if(i*c[i]>sum)//完全背包
{
for(j = i; j<=sum; j++)
dp[j] = dp[j]>dp[j-i]+i? dp[j]:dp[j-i]+i;
}
else
{
k = 1;
while(k<c[i])//2进制拆分
{
zero_one(k*i, k*i);
c[i] -= k;
k *= 2;
}
zero_one(c[i]*i, c[i]*i);
}
if(dp[sum] == sum)
break;
}
if(dp[sum] == sum)
printf("Can be divided.\n");
else
printf("Can't be divided.\n");
}
printf("\n");
}
return 0;
}
code：
#include <stdio.h>
#include <string.h>
int sum = 0, c[12], used[20002*6], f[20002*6];
int main()
{
int i = 0, j = 0, k = 0, count = 0;
while(1)
{
sum = 0;
for(i = 1; i<=6; i++)
{
scanf("%d", &c[i]);
sum += i*c[i];
}
if(!sum)
break;
printf("Collection #%d:\n",++count);
if(sum%2 == 1)
printf("Can't be divided.\n");
else www.zzzyk.com
{
sum /= 2;
memset(f, 0, sizeof(f));
f[0] = 1;
for(i = 1; i<=6; i++)
{
memset(used, 0, sizeof(used));
for(j = i; j<=sum; j++)
{
if(!f[j] && f[j-i] && used[j-i]<c[i])
补充：软件开发 , C语言 ,
