题意：货币系统有 N 种不同面值的钱，每种钱的价值分别为 V1,V2,…,VN 一个人要买价值和为 T 的商品，他每种分别相应的带了 C1,C2,…,CN ，然后问你交易完成后所需要经手的钱币最少数目
思路：先对人进行多重背包，然后对售货员进行完全背包
一直情况就是那个人所带的钱刚好凑成了 T ，那么就不需要找钱了，，否则就需要找钱，相当于那个人支付了他所能付的超过 T 的钱 M，然后售货员找钱 M-T ，把这两者的经手的钱数加起来就行了
初始化的时候除了 dp[0]=0 之外，其它的都为 inf 表示 i 这个状态是可以由商品组合起来的
否则如果全部初始化为 0 的话，i 只能说是一个上界
我们不应该把10000当做背包的容量，因为付款可能超过T的最大值。
代码：
#include <stdio.h>#include <string.h>#define MAX 20100#define INF 1000000000int dpx[MAX] , dpy[MAX];int v[110] , c[110] , total;int min(int a , int b){return a>b?b:a ;}void zeroOnePack(int dp[] , int v , int c){for(int i = MAX-1 ; i >= v ; –i){dp[i] = min(dp[i],dp[i-v]+c) ;}}void completePack(int dp[] , int v){for(int i = v ; i < MAX ; ++i){dp[i] = min(dp[i],dp[i-v]+1) ;}}void multiplePack(int dp[] , int v, int c){if(c*v>=total){completePack(dp,v) ;}else{int k = 1 ; while(k<c){zeroOnePack(dp , k*v,k) ;c -= k ;k *= 2 ;}zeroOnePack(dp,c*v,c) ;}}int main(){int n , t = 1;while(~scanf("%d%d",&n,&total) && (n+total)){for(int i = 1 ; i < MAX ; ++i){dpx[i] = INF ;dpy[i] = INF ;}dpx[0] = dpy[0] = 0 ;for(int i = 0 ; i < n ; ++i ){scanf("%d",&v[i]) ;}for(int i = 0 ; i < n ; ++i ){scanf("%d",&c[i]) ;}for(int i = 0 ; i < n ; ++i){multiplePack(dpx,v[i],c[i]) ;}for(int i = 0 ; i < n ; ++i){for(int j = v[i] ; j < MAX ; ++j){dpy[j] = min(dpy[j-v[i]]+1,dpy[j]) ;}}int ans = INF ;printf("Case %d: ",t++) ;for(int i = total ; i < MAX ; ++i){ans = min(dpx[i]+dpy[i-total] , ans) ;}if(ans == INF){puts("-1") ;}else{printf("%d\n",ans) ;}}return 0 ;}
我知道按攻略去旅行的人往往玩得过于按步就班，
