题目连接：点击打开链接
题目大意：John有N种货币，每种货币有相应的价值V和数量C，他要用仅有的货币去买价值为T的货物，问：付的硬币数目和找回的硬币数目最少为多少个？
解题思路：John的货币是有限的，所以可以用多重背包求解出买价值为T的货物最少要花的货币数目，卖家的货币数目是无限的，所以可以用完全背包计算出卖家找钱的最少数目；最后用两个数组遍历出参与交易最少的货币数就可以了。思路是这样的，但是有个大考点就是：如何确定两个背包的背包上限？我一开始将John获得的最大面值的货币总额作为背包上限，可是Runtime了，后来了解到了鸽笼原理，具体如下：
John的付款数最多为maxv*maxv+m
证明如下：
如果John的付款数大于了maxv*maxv+m，即付硬币的数目大于了maxv，根据鸽笼原理，至少有两个的和对maxv取模的值相等(这个意思应该是:至少maxv+1个硬币对maxv求余,然后余数属于[0,maxv-1]范围,肯定有至少两个硬币的余数相同的)，也就是说，这部分硬币能够用更少的maxv来代替。（通俗的来说就是可以用更少的大钱换很多的小钱，金币数就少了）。
于是我把背包数组开到20000...成功过了！ 具体代码如下，注释很详细。
代码如下： （有个注释的代码，是我前面提到的导致我RT的地方）
#include<iostream> #include<string.h> #include<algorithm> #define INF 999999999 using namespace std; int dp1[20005],dp2[20005]; int main() { int n,m; while(cin>>n>>m) { memset(dp1,0,sizeof(dp1)); memset(dp2,0,sizeof(dp2)); int val[150],num[150]; // int maxnv=0; for(int i=1; i<=n; i++) { cin>>val[i]; //if(maxnv<val[i]) // maxnv=val[i]; } // int W=maxnv*maxnv+m; for(int i=1; i<=n; i++) cin>>num[i]; for(int i=1; i<=20000; i++) dp1[i]=dp2[i]=INF; dp1[0]=dp2[0]=0; int i,j,k; for(i=1; i<=n; i++) //用多重背包转化为01背包求解最少付多少硬币 { for(k=1; k<=num[i]; k*=2) { for(j=20000; j>=k*val[i]; j--) { dp1[j]=min(dp1[j],dp1[j-k*val[i]]+k); } num[i]-=k; } for(j=20000; j>=num[i]*val[i]; j--) { dp1[j]=min(dp1[j],dp1[j-num[i]*val[i]]+num[i]); } } for(int i=1; i<=n; i++) //用完全背包求解找钱的最少硬币数量 { for(int j=val[i]; j<=20000; j++) dp2[j]=min(dp2[j],dp2[j-val[i]]+1); } int ans=INF; for(int i=m; i<=20000; i++) { ans=min(ans,dp1[i]+dp2[i-m]); } if(ans==INF) cout<<-1<<endl; else cout<<ans<<endl; } return 0; }
~step by step
