题目链接：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[110],num[110],a[N]; int n,m,tot; int solve() { for(int i=0;i<=m;i++)dp[i]=0; for(int i=1;i<tot;i++) { for(int j=m;j>=a[i];j--) dp[j]=max(dp[j],dp[j-a[i]]+a[i]); } int sum=0; for(int i=1;i<=m;i++)if(dp[i]==i)sum++; return sum; } int main() { while(scanf("%d%d",&n,&m)&&(n+m)) { for(int i=1;i<=n;i++)scanf("%d",&val[i]); for(int i=1;i<=n;i++)scanf("%d",&num[i]); tot=1; for(int i=1;i<=n;i++) { for(int j=1;j<=num[i];j*=2) { a[tot++]=val[i]*j; num[i]-=j; } if(num[i])a[tot++]=num[i]*val[i]; } int ans=solve(); printf("%d ",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[110],num[110],used[N];//i元钱时某种钱用的次数 int n,m; int solve() { int sum=0; for(int i=0;i<=m;i++)dp[i]=0; dp[0]=1; for(int i=1;i<=n;i++) { memset(used,0,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]=1;used[j]=used[j-val[i]]+1;sum++; } } } return sum; } int main() { while(scanf("%d%d",&n,&m)&&(n+m)) { for(int i=1;i<=n;i++)scanf("%d",&val[i]); for(int i=1;i<=n;i++)scanf("%d",&num[i]); int ans=solve(); printf("%d ",ans); } }