题目描述
组合背包：有的物品只可以取一次（01背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限（多重背包）。
DD大牛的伪代码
for i = 1 to N
if 第i件物品属于01背包
ZeroOnePack(F,Ci,Wi)
else if 第i件物品属于完全背包
CompletePack(F,Ci,Wi)
else if 第i件物品属于多重背包
MultiplePack(F,Ci,Wi,Ni)输入
第一个数为数据组数n 1<=n<=10
接下来n组测试数据，每组测试数据由2部分组成。
第一行为背包容量V，物品种类数N。1<=V<=30000,1<=N<=200
接下来N行每行三个数为物品价值v，物品重量w，物品件数M。M=233表示物品无限。
1<=v,w<=200, 1<=M<=25
输出
对于每组数据，输出一行，背包能容纳的最大物品价值
输入样例
1
10 3
2 2 233
3 2 1
4 3 3输出样例
13
题目来源：http://biancheng.love/contest/10/problem/F/index
解题思路：
组合背包：0-1背包、完全背包、多重背包。
因此需要结合上述三种背包问题的解决方法来solve组合背包
0-1背包代码：
void Zeronepack(int w,int v)
{
for(int i=V; i>=w; i--)
if(dp[i]<dp[i-w]+v)
dp[i]=dp[i-w]+v;
}
完全背包代码：
void Compack(int w,int v)
{
for(int i=w; i<=V; i++)
if(dp[i]<dp[i-w]+v)
dp[i]=dp[i-w]+v;
}
多重背包代码：
void Multipack(int w,int v,int num)
{
int k;
if(w*num>=V)
{
Compack(w,v);
return;
}
for(k=; k<num; k<<)
{
Zeronepack(k*w,k*v);
num-=k;
}
Zeronepack(num*w,num*v);
}
本题组合背包代码：
#include <bits/stdc++.h>
int dp[];
int V,N; void Compack(int w,int v)
{
for(int i=w; i<=V; i++)
if(dp[i]<dp[i-w]+v)
dp[i]=dp[i-w]+v;
} void Zeronepack(int w,int v)
{
for(int i=V; i>=w; i--)
if(dp[i]<dp[i-w]+v)
dp[i]=dp[i-w]+v;
} void Multipack(int w,int v,int num)
{
int k;
if(w*num>=V)
{
Compack(w,v);
return;
}
for(k=; k<num; k<<)
{
Zeronepack(k*w,k*v);
num-=k;
}
Zeronepack(num*w,num*v);
} int main()
{
int kase,v,w,m;
scanf("%d",&kase);
while(kase--)
{
memset(dp,,sizeof(dp));
scanf("%d%d",&V,&N);
for(int i=;i<=N;i++)
{
scanf("%d%d%d",&v,&w,&m);
if(m==)
Zeronepack(w,v);
else if(m==)
Compack(w,v);
else
Multipack(w,v,m);
}
printf("%d\n",dp[V]);
}
return ;
}