题目链接：http://acm.split.hdu.edu.cn/showproblem.php?pid=1059
之前写过一个多重背包二进制优化的博客，不懂请参考：http://www.cnblogs.com/a-clown/p/5953847.html
//之前WA了无数次。。心塞。。。
两种思路，都可以。
代码1：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
#define ll long long int p[],w[],c[];
int dp[]; int main()
{
int T;
cin>>T;
while(T--)
{
int n,m;
cin>>n>>m;
for(int i=; i<=m; i++)
cin>>p[i]>>w[i]>>c[i];
memset(dp,,sizeof(dp));
for(int i=; i<=m; i++)
{
if(p[i]*c[i]>m)
{
for(int j=p[i]; j<=n; j++)
dp[j]=max(dp[j],dp[j-p[i]]+w[i]);
}
else
{
int k=;
for(int j=; c[i]>; j<<=)
{
int temp=min(j,c[i]);
for(int q=n; q>=temp*p[i]; q--)
dp[q]=max(dp[q],dp[q-p[i]*temp]+w[i]*temp);
c[i]-=j;
}
}
}
cout<<dp[n]<<endl;
}
return ;
}
代码2：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=2e5+; int a[];
int dp[maxn]; int main()
{
int t=;
while(scanf("%d",&a[])==)
{
int sum=a[];
for(int i=; i<=; i++)
{
scanf("%d",&a[i]);
sum+=a[i]*i;
}
if(sum==) break;
if(sum%==)
{
printf("Collection #%d:\n",++t);
puts("Can't be divided.");
puts("");
}
else
{
printf("Collection #%d:\n",++t);
memset(dp,,sizeof(dp));
dp[]=;
int ans=sum/;
for(int i=; i<=; i++)
{
int n=a[i];
for(int j=; n>; j<<=)
{
int temp=min(j,n);
for(int k=ans-i*temp; k>=; k--)
if(dp[k])dp[k+i*temp]=;
n-=j;
}
}
if(dp[ans]) puts("Can be divided.\n");
else puts("Can't be divided.\n"); }
}
return ;
}