*题意：
给定一定的金额cash，在给出n中货币，每种货币有一定的数量。问：在不超过cash的条件下，用给定货币组成最接近cash的金额数是多少。
*思路：
完全背包问题+数量限制。要实现并不困难，不过由于数据较大，以上思路有三重循环会TLE。所以，必须优化。至于优化，可以选择二进制优化，或者把循环去掉一层。
1.二进制优化是把物品个数用二进制数表示出来，以减少循环次数。
2.去掉物品书的那层循环：因为我们在计算dp[i+1][j]，枚举物品数量k>=1的情况时，与在计算
dp[i+1][j-d[i]]，枚举的k>0的情况恰好相同，所以我们可以不用在用到k循环达到优化的效果。
二维数组：
#include<iostream> #include<cstring> using namespace std; int dp[11][100005]; int count[11][100005]; int main() { int cash,i,j,n; int d[11],q[11]; while(cin>>cash>>n) { memset(dp,0,sizeof(dp)); for(i=0;i<n;i++) cin>>q[i]>>d[i]; for(i=0;i<n;i++) { memset(count,0,sizeof(count)); for(j=d[i];j<=cash;j++) { if(i>0) dp[i][j]=dp[i-1][j]; if(dp[i][j]<dp[i][j-d[i]]+d[i]&&count[i][j-d[i]]<q[i]) { dp[i][j]=dp[i][j-d[i]]+d[i]; count[i][j]=count[i][j-d[i]]+1; } } } if(n==0) cout<<0<<endl; else cout<<dp[n-1][cash]<<endl; } return 0; }
一维数组优化：
#include<iostream> #include<cstring> using namespace std; int dp[100002]; int c[100002]; int main() { int cash,i,j,k,n; int d[11],q[11]; while(cin>>cash>>n) { memset(dp,0,sizeof(dp)); for(i=0;i<n;i++) cin>>q[i]>>d[i]; for(i=0;i<n;i++) { memset(c,0,sizeof(c)); for(j=d[i];j<=cash;j++) { if(dp[j]<dp[j-d[i]]+d[i]&&c[j-d[i]]<q[i]) { dp[j]=dp[j-d[i]]+d[i]; c[j]=c[j-d[i]]+1; } } } if(n==0) cout<<0<<endl; else cout<<dp[cash]<<endl; } return 0; }