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&#39;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&#39;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&#39;t be divided.\n");

else

{

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&#39;t be divided.\n");

}

printf("\n");

}

return 0;

}

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/tongxinshuyu/article-22995-1.html