HDU 3591 The trouble of Xiaoqian

The trouble of Xiaoqian

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Problem Description

In the country of ALPC , Xiaoqian is a very famous mathematician. She is immersed in calculate, and she want to use the minimum number of coins in every shopping. (The numbers of the shopping include the coins she gave the store and the store backed to her.)
And now , Xiaoqian wants to buy T (1 ≤ T ≤ 10,000) cents of supplies. The currency system has N (1 ≤ N ≤ 100) different coins, with values V1, V2, …, VN (1 ≤ Vi ≤ 120). Xiaoqian is carrying C1 coins of value V1, C2 coins of value V2, …, and CN coins of value VN (0 ≤ Ci ≤ 10,000). The shopkeeper has an unlimited supply of all the coins, and always makes change in the most efficient manner .But Xiaoqian is a low-pitched girl , she wouldn’t like giving out more than 20000 once.

Input

There are several test cases in the input.
Line 1: Two space-separated integers: N and T.
Line 2: N space-separated integers, respectively V1, V2, …, VN coins (V1, …VN)
Line 3: N space-separated integers, respectively C1, C2, …, CN
The end of the input is a double 0.

Output

Output one line for each test case like this ”Case X: Y” : X presents the Xth test case and Y presents the minimum number of coins . If it is impossible to pay and receive exact change, output -1.

Sample Input

3 70
5 25 50
5 2 1
0 0

Sample Output

Case 1: 3

思路：

看起来挺难的，做起来也不太简单，但是思路懂了，就好做多了，实际上这题就是完全背包+多种背包，
1.因为老板的资金是无穷的，所以老板这块就是用完全背包，然后就是套用完全背包的模板就行了，而为什么要到mx（也就是最大价值的平方）？因为你无法确定钱该如何找零，不同面额的钱，找零不同，比如10000或者1000付你70，你的找零就是不同的了。
2.然后就是多重背包了，因为钱币数量有限，所以首先想到的就是多重背包了，多重背包的第二个循环是倍数，也就是针对钱币的数量用的第三个循环有点像01背包，也就是在01背包的基础上多了数量的关系，也就多了第二个循环了，（01背包每件物品数量为1，但是多重背包数量就不是了），后面的if的作用就是因为第二个循环是用每次乘以2，所以可能会有剩余，所以用个if把剩余的清理掉，假如不乘2的话改成每次加一就不用if了，但是时间复杂度大了很多（这题是没有超时的）。
3.最后就是输出了，从需要付款的钱开始遍历，一个付钱，一个找零，付钱i，找零i-m。输出的时候格式要注意了，在格式上 ，我wa了三次，就是输出-1的时候的格式。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxnv = 120;
const int maxnm = 10010;
const int maxn = 110;
const int x = maxnv * maxnv + maxnm;
const long long inf = 0x3f3f3f3f;
int dpout[x], dpin[x], v[110], c[110];
int main() {
    int n, m, cnt = 1;
    while (scanf("%d %d", &n, &m) != EOF && n + m) {
        int mx = 0, sum = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &v[i]);
            mx = max(mx, v[i] * v[i]);
        }
        for (int i = 1; i <= n; i++) {
            scanf("%d", &c[i]);
            sum += c[i] * v[i];
        }
        if (sum < m) {
            printf("Case %d: -1\n", cnt++);
            continue;
        } 
        fill(dpin, dpin + x, inf);
        fill(dpout, dpout + x, inf);
        dpin[0] = dpout[0] = 0; 
        for (int i = 1; i <= n; i++) {
            for (int j = v[i]; j <= mx; j++) {
                dpout[j] = min(dpout[j], dpout[j - v[i]] + 1);
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= c[i]; j <<= 1) {
                for (int k = mx; k >= v[i] * j; k--) {
                    dpin[k] = min(dpin[k], dpin[k - j * v[i]] + j);
                }
                c[i] -= j;
            }
            if (c[i] > 0) {
                for (int k = mx; k >= c[i] * v[i]; k--) {
                    dpin[k] = min(dpin[k], dpin[k - c[i] * v[i]] + c[i]);
                }
            }
        }
        int ans = inf;
        for (int i = m; i <= mx + m; i++) {
            ans = min(ans, dpin[i] + dpout[i - m]);
        } 
        if (ans == inf) printf("Case %d: -1\n", cnt++);
        else printf("Case %d: %d\n", cnt++, ans);
    }
    return 0;
}