題目大意：有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.2cto.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])
{
f[j] = 1;
used[j] = used[j-i]+1;
}
}
if(f[sum])
break;
}
if(f[sum])
printf("Can be divided.\n");
else
printf("Can't be divided.\n");
}
printf("\n");
}
return 0;
}
作者：ulquiorra0cifer
