学步园

http://acm.hdu.edu.cn/showproblem.php?pid=1059

解题思路：给你6种价值不一样的东西，并且每种物品都有一定的数量，现在问你，你可以把他们平均分成两份价值一样的吗？？

解题思路：多重背包问题

比较笨拙的代码

#include <stdio.h><br /> #include <string.h><br /> #include <math.h><br /> #define Max(a,b) a>b?a:b<br /> #define Size 100005<br /> int c[2*Size],w[2*Size],dp[200005];<br /> int main()<br /> {<br /> int sum,i,num[7],no = 1,len,j,k,tem;<br /> while (1)<br /> {<br /> sum = 0;<br /> for (i=1;i<=6;i++)<br /> {<br /> scanf("%d",&num[i]);<br /> sum+=num[i]*i;<br /> }<br /> if(!sum)<br /> break;<br /> if(sum&1)<br /> else<br /> {<br /> len = 0;<br /> for (i=1;i<=6;i++)<br /> {<br /> /*二进制划分,转成01背包做*/<br /> if(num[i])<br /> {<br /> k =(int)(log(num[i]+1)/log(2))-1;<br /> for (j=0;j<=k;j++)<br /> {<br /> c[len] = w[len] = (int)(pow(2.0,j)*i);<br /> len++;<br /> }<br /> tem = (int)(pow(2.0,k+1))-1;<br /> if(num[i]!=tem)<br /> {<br /> c[len] = w[len] = (num[i]-tem)*i;<br /> len++;<br /> }<br /> }<br /> }<br /> for(i=0;i<=sum;i++)<br /> dp[i] = 0;<br /> for (i=0;i<len;i++)<br /> {<br /> for (j = sum/2;j>=c[i];j--)<br /> {<br /> dp[j] = Max(dp[j],dp[j-c[i]]+w[i]);<br /> }<br /> }<br /> if(dp[sum/2] == sum/2)<br /> printf("Collection #%d:/nCan be divided./n/n",no++);<br /> else<br /> printf("Collection #%d:/nCan't be divided./n/n",no++);<br /> }<br /> }<br /> return 0;<br /> }

参考背包问题后，学习的代码

#include <stdio.h><br /> #include <string.h><br /> #define Size 60005<br /> #define Max(a,b) a>b?a:b<br /> int sum;<br /> int dp[Size];<br /> /*01背包*/<br /> void ZeroOnePack(int cost,int weight)<br /> {<br /> int i;<br /> for(i = sum;i>=cost;i--)<br /> dp[i] = Max(dp[i],dp[i-cost]+weight);<br /> }<br /> /*完全背包*/<br /> void CompletePack(int cost,int weight)<br /> {<br /> int i;<br /> for(i=cost;i<=sum;i++)<br /> dp[i] = Max(dp[i],dp[i-cost]+weight);<br /> }<br /> /*多重背包*/<br /> void MulPack(int cost,int weight,int count)<br /> {<br /> int i;<br /> if(cost*count>=sum)<br /> {<br /> CompletePack(cost,weight);<br /> return ;<br /> }<br /> i = 1;<br /> /*二进制划分*/<br /> while (i<count)<br /> {<br /> ZeroOnePack(i*cost,i*weight);<br /> count-=i;<br /> i<<=1;<br /> }<br /> ZeroOnePack(count*cost,count*weight);<br /> }<br /> int main()<br /> {<br /> int num[7],no = 1,i;<br /> while (1)<br /> {<br /> sum = 0;<br /> for(i=1;i<=6;i++)<br /> {<br /> scanf("%d",&num[i]);<br /> sum+=num[i]*i;<br /> }<br /> if(!sum)<br /> break;<br /> if(sum&1)<br /> printf("Collection #%d:/nCan't be divided./n/n",no++);<br /> else<br /> {<br /> sum>>=1;<br /> for(i=0;i<=sum;i++)<br /> dp[i] = 0;<br /> for(i=1;i<=6;i++)<br /> if(num[i])<br /> MulPack(i,i,num[i]);<br /> if(dp[sum] == sum)<br /> printf("Collection #%d:/nCan be divided./n/n",no++);<br /> else<br /> printf("Collection #%d:/nCan't be divided./n/n",no++);<br /> }<br /> }<br /> return 0;<br /> }