题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2844
题意：一位同学想要买手表，他有n种硬币，每种硬币已知有num[i]个。已知手表的价钱最多m元，问她用这些钱能够凑出多少种价格来买手表。
分析：二进制优化的多重背包，假设每种硬币为容量为val[i]且价值也为val[i]的物品，最后有dp[i]==i则能组成价格为i。因为容量为i能达到的最大价值也是i，刚好符合01背包的含义。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <stack>
#include <vector>
#include <set>
#include <map>
#define LL long long
#define mod 1000000007
#define inf 0x3f3f3f3f
#define N 100010
using namespace std;
int dp[N],val[],num[],a[N];
int n,m,tot;
int solve()
{
for(int i=;i<=m;i++)dp[i]=;
for(int i=;i<tot;i++)
{
for(int j=m;j>=a[i];j--)
dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
}
int sum=;
for(int i=;i<=m;i++)if(dp[i]==i)sum++;
return sum;
}
int main()
{
while(scanf("%d%d",&n,&m)&&(n+m))
{
for(int i=;i<=n;i++)scanf("%d",&val[i]);
for(int i=;i<=n;i++)scanf("%d",&num[i]);
tot=;
for(int i=;i<=n;i++)
{
for(int j=;j<=num[i];j*=)
{
a[tot++]=val[i]*j;
num[i]-=j;
}
if(num[i])a[tot++]=num[i]*val[i];
}
int ans=solve();
printf("%d\n",ans);
}
}
这题由于数据量较大，就算是二进制优化的多重背包也是998ms险过。这里可以增加一个一维数组use[ i ],记录到达i元时第j种钱用的次数。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <stack>
#include <vector>
#include <set>
#include <map>
#define LL long long
#define mod 1000000007
#define inf 0x3f3f3f3f
#define N 100010
using namespace std;
int dp[N],val[],num[],used[N];//i元钱时某种钱用的次数
int n,m;
int solve()
{
int sum=;
for(int i=;i<=m;i++)dp[i]=;
dp[]=;
for(int i=;i<=n;i++)
{
memset(used,,sizeof(used));//每次初始化第i种钱用了0次
for(int j=val[i];j<=m;j++)
{
if(!dp[j]&&dp[j-val[i]]&&used[j-val[i]]<num[i])//到达j元用的i种钱的次数是到达 j-val[i]元用的次数加1
{
dp[j]=;used[j]=used[j-val[i]]+;sum++;
}
}
}
return sum;
}
int main()
{
while(scanf("%d%d",&n,&m)&&(n+m))
{
for(int i=;i<=n;i++)scanf("%d",&val[i]);
for(int i=;i<=n;i++)scanf("%d",&num[i]);
int ans=solve();
printf("%d\n",ans);
}
}