ps：原来用新浪，可是代码的排版不是很好，所以用博客园啦，先容许我把从八月份开始的代码搬过来，从这里重新出发，希望这里可以一直见证我的成长。
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 12337 Accepted Submission(s): 4925
You are to write a program which reads n,m,A1,A2,A3...An and C1,C2,C3...Cn corresponding to the number of Tony's coins of value A1,A2,A3...An then calculate how many prices(form 1 to m) Tony can pay use these coins.
1 2 4 2 1 1
2 5
1 4 2 1
0 0
#include<iostream>
#include<string.h>
using namespace std;
const int N=100005;
int a[N],b[N],dp[N];
int i,j;
int max(int a,int b)
{
return a<b?b:a;
} void onepack(int c,int w,int m)
{
for(j=m;j>=c;j--)
dp[j]=max(dp[j],dp[j-c]+w);
}
void allpack(int c,int w,int m)
{
for(j=c;j<=m;j++)
{
dp[j]=max(dp[j],dp[j-c]+w);
}
} void mulpack(int c,int w,int m,int n)
{
if(c*n>=m) allpack(c,w,m);
else
{
int k=1;
while(k<n)//二进制优化，下面有具体说明
{
onepack(k*c,k*w,m);
n-=k;
k*=2;
}
onepack(n*c,n*w,m); }
} int main()
{
int n,m; while(cin>>n>>m,n||m)
{
for(i=1;i<=n;i++)
cin>>a[i];
for(i=1;i<=n;i++)
cin>>b[i];
memset(dp,0,sizeof(dp));
for(i=1;i<=n;i++)
{
mulpack(a[i],a[i],m,b[i]);
}
int cnt=0;
for(i=1;i<=m;i++)
if(dp[i]==i) cnt++;
cout<<cnt<<endl;
}
return 0;
}
这是一个多重背包的模板，也是十分好用的一种模板，因为这个比直接拆除01 背包来做
要省些时间。这是为啥呢，首先先由我讲一下为什么能换成01 背包吧。
举个栗子吧。 假如给了我们 价值为 2，但是数量却是10 的物品，我们应该把10给拆开，要知道二进制可是能够表示任何数的，所以10 就是可以有1，2, 4，8之内的数把它组成，一开始我们选上 1了，然后让10-1=9，再选上2,9-2=7，在选上 4,7-4=3，
而这时的3<8了，所以我们就是可以得出 10由 1,2,4,3，来组成，就是这个数量为1,2,3,4的物品了，那么他们的价值是什么呢，是2,4,6,8，也就说给我们的价值为2，数量是10的这批货物，已经转化成了价值分别是2,4,6,8元的货物了，每种只有一件哎！！！！这就是二进制优化的思想。
那为什么会有完全背包和01 背包的不同使用加判断呢？原因也很简单啊，当数据很大，大于背包的容纳量时，我们就是在这个物品中取上几件就是了，取得量时不知道的，也就理解为无限的啦，这就是完全背包啦，反而小于容纳量的就是转化为01背包来处理就是了，可以大量的省时间。