题意：

消费者有n种硬币，每种硬币的价值为v[i]， 数量为c[i]，而超市有消费者拥有的每一种硬币，且每种有无限个，每次去买东西， 如果要找钱的话， 超市会给你最少的硬币数， 给你一个数t，要你求出，最少需要用到的硬币数量在本次交易中（消费者需要携带的硬币数量 + 超市找钱给的硬币数量）。（t<= 20000）

题解：

对超市进行完全背包

对消费者进行多重背包

加入消费者的某种硬币的总价值大于最大值，那么可以进行对其完全背包

 

 

/*
Algorithm: 完全背包 + 多重背包
Author: anthony1314
Creat Time:
Time Complexity:
*/

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#include<stack>
#include<cstring>
#include<cstdio>
//#include<bits/stdc++.h>
#define ll long long
#define maxn 1005
#define mod 1e9 + 7
#define line printf("--------------");
using namespace std;
#define inf 0x3f3f3f3f
#define mm 20005
#define maxn 105
int v[maxn], c[maxn];
int dp1[mm], dp2[mm];
int n, t;
void zero_one_bag(int *dp, int vv, int cc) { // vv代表价值  cc代表硬币数量
    for(int i = 20000; i >= vv; i--) { //逆序
        dp[i] = min(dp[i-vv] + cc, dp[i]);
    }
}
void com_bag(int *dp, int vv) {//完全背包
    for(int i = vv; i <= 20000; i++) {//正序
        dp[i] = min(dp[i], dp[i-vv] + 1);//每次加1
    }
}
void many_bag(int *dp, int vv, int cc) {//多重背包
    if(vv * cc >= 20000) {//总价值超过最大可以直接完全背包
        com_bag(dp, vv);
        return ;
    }
    int k = 1;
    while(k < cc) {//多重背包 2进制优化 
        zero_one_bag(dp, vv*k, k);
        cc -= k;
        k *= 2;
    }
    zero_one_bag(dp, vv*cc, cc);
}
int main() {
    int ccc = 1;
    while(cin>>n>>t) {
        if(n == 0 && t == 0) {
            break;
        }
        for(int i = 1; i <= n; i++) {
            scanf("%d", &v[i]);
        }
        for(int i = 1; i <= n; i++) {
            scanf("%d", &c[i]);
        }

        memset(dp1, inf, sizeof(dp1));
        memset(dp2, inf, sizeof(dp2));
        dp1[0] = dp2[0] = 0;
        for(int i = 1; i <= n; i++) {
            many_bag(dp1, v[i], c[i]);
        }
        for(int i = 1; i <= n; i++){
            com_bag(dp2, v[i]);
        }
        int ans = dp1[t];
        for(int i = t+1; i <= 20000; i++){
            ans = min(ans, dp1[i] + dp2[i-t]);
        }
        printf("Case %d: ", ccc++);
        if(ans == inf){
            cout<<"-1"<<endl;
            continue;
        }
        cout<<ans<<endl;
    }
    return 0;
}