题目大意：给你n个种类的钱和对应的数量，同统计一下从1到m能够凑成的钱有多少个；

解题思路：多重背包的题，少了一个类似于重量上限的限制，这里其实就是那个m，每次不断变化的1到m的值就是限制，最后统计下多少dp数组更新过就是能够凑到的，这里不用从1到m枚举上限，直接上限填m，这样在更新完n个种类后m之前由于要到达m必然解决比他小的包，简言之，就是前面的dp已经优化了（你想我们既然都优化到m了，像m-1,m-2,m-3...2,1这些是不是都优化了），以下模板。（ps：HDOJ这题我交了一个有BUG的代码上去居然AC了，虽然是998ms

AC代码如下：

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<queue>
#include<map>
#include<math.h>
using namespace std;

const int inf=0x3f3f3f3f;
const int maxn=1e5+10;

int dp[maxn],value[110],num[110];

int max(int a,int b)
{
	return a>b?a:b;
}
//每次最大值会更新
void pack01(int v,int h,int m)
{
	for(int i=m;i>=v;i--)
		dp[i]=max(dp[i],dp[i-v]+h);
	return ;
}

void packall(int v,int h,int m)
{
	for(int i=v;i<=m;i++)
		dp[i]=max(dp[i],dp[i-v]+h);
	return ;
}

void packs(int v,int h,int m,int cnt)
{
	if(cnt*v>=m)
	{
		packall(v,h,m);
		return ;
	}
	int k=1;
	while(k<=cnt)
	{
		pack01(k*v,k*h,m);  //更新物品的比例
		cnt-=k;  //二进制思路压缩背包物品的数量
		k<<=1;
	}
	if(cnt)
		pack01(cnt*v,cnt*h,m);  //最后一件
	return ;
}
/*
dp[i]:不超过i的合成的最大的钱
*/
int main()
{
	int n,m,cnt,i,j;
	while(cin>>n>>m && n+m)
	{
		dp[0]=cnt=0;
		for(i=1;i<=m;i++)
			dp[i]=-inf;
		for(i=0;i<n;i++)
			cin>>value[i];
		for(i=0;i<n;i++)
			cin>>num[i];
		for(j=0;j<n;j++)
			packs(value[j],value[j],m,num[j]);
		for(i=1;i<=m;i++)
			if(dp[i]>0)
				cnt++;
		cout<<cnt<<endl;
	}
	return 0;
}

View Code

Problem : 2844 ( Coins )     Judge Status : Accepted
RunId : 23886175    Language : C++   
Code Render Status : Rendered By HDOJ C++ Code Render Version 0.01 Beta 
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<queue>
#include<map>
#include<math.h>
using namespace std; const int inf=0x3f3f3f3f; const int maxn=1e5+10; int dp[maxn],value[110],num[110]; int max(int a,int b) { return a>b?a:b; }
//每次最大值会更新
void pack01(int v,int h,int m) { for(int i=m;i>=v;i--)
        dp[i]=max(dp[i],dp[i-v]+h); return ; } void packall(int v,int h,int m) { for(int i=v;i<=m;i++)
        dp[i]=max(dp[i],dp[i-v]+h); return ; } void packs(int v,int h,int m,int cnt) { if(cnt*v>=m) {
        packall(v,h,m); return ; } int k=1; while(k<=cnt) {
        pack01(k*v,k*h,m);  //更新物品的比例
        cnt-=k;  //二进制思路压缩背包物品的数量
        k<<1; //bug的地方 }
    pack01(cnt*v,cnt*h,m);  //最后一件
 return ; }
/*
dp[i]:不超过i的合成的最大的钱
*/ int main() { int n,m,cnt,i,j; while(cin>>n>>m && n+m) {
        dp[0]=cnt=0; for(i=1;i<=m;i++)
            dp[i]=-inf; for(i=0;i<n;i++)
            cin>>value[i]; for(i=0;i<n;i++)
            cin>>num[i]; for(j=0;j<n;j++)
            packs(value[j],value[j],m,num[j]); for(i=1;i<=m;i++) if(dp[i]>0)
                cnt++;
        cout<<cnt<<endl; } return 0; }