poj1014多重背包模板

题意：有六种石头，给你各种石头的个数，每种石头的价值就是其输入的顺序，求是否有一种方法可以分这些石头为两个相等的部分。
解题思路：多重背包，其实说是可行性背包更贴切，只不过这里用的是多重背包的模板，因为每一种石头都有一定的数量，用多重背包来做好一点。就是以总价值的一半为下标的上界（总价值可被2乘除时），待dp完成后查看，查当容量为总价格的一半的时候，是否存在可取的石头数。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n,w[20005],p,m,c[20005],dp[120005];
int main()
{
int sum,i,j,k,t=0;
while(1)
{
sum=m=n=0;
for(i=0;i<6;i++)
{
scanf("%d",&p);
n+=p;
sum+=p*(i+1);
k=1;
while(k<p)
{
c[m]=(i+1)*k;
w[m]=k;
m++;
p=p-k;
k=k*2;
}
if(p!=0)
{
c[m]=(i+1)*p;
w[m]=p;
m++;
}
}
if(n==0) break;
if(sum%2!=0)
{
printf("Collection #%d:\nCan‘t be divided.\n",++t);
}
else
{
sum=sum/2;
memset(dp,-1,sizeof(dp));
dp[0]=0;
for(i=0;i<m;i++)
for(j=sum;j>=c[i];j--)
if(dp[j-c[i]]>=0)
dp[j]=max(dp[j],dp[j-c[i]]+w[i]);
if(dp[sum]>=0)
printf("Collection #%d:\nCan be divided.\n",++t);
else
printf("Collection #%d:\nCan‘t be divided.\n",++t);
}
printf("\n");
}
return 0;
}

本文出自 “Qero” 博客，请务必保留此出处http://8590696.blog.51cto.com/8580696/1358904

poj1014多重背包模板

原文：http://8590696.blog.51cto.com/8580696/1358904