題目

男人八題 之 Coins

Description

People in Silverland use coins.They have coins of value A1,A2,A3...An Silverland dollar.One day Tony opened his money-box and found there were some coins.He decided to buy a very nice watch in a nearby shop. He wanted to pay the exact price(without change) and he known the price would not more than m.But he didn't know the exact price of the watch. 
You are to write a program which reads n,m,A1,A2,A3...An and C1,C2,C3...Cn corresponding to the number of Tony's coins of value A1,A2,A3...An then calculate how many prices(form 1 to m) Tony can pay use these coins. 
Input

The input contains several test cases. The first line of each test case contains two integers n(1<=n<=100),m(m<=100000).The second line contains 2n integers, denoting A1,A2,A3...An,C1,C2,C3...Cn (1<=Ai<=100000,1<=Ci<=1000). The last test case is followed by two zeros.
Output

For each test case output the answer on a single line.
Sample Input

3 10
1 2 4 2 1 1
2 5
1 4 2 1
0 0
Sample Output

8
4

具體的意思就是每組數(shù)據(jù)包含 n 中硬幣倦炒，表的最大可能的價(jià)格是 m眼姐，A1,A2,A3...An 分別代表每種硬幣的價(jià)值，C2,C3...Cn 代表每種硬幣的數(shù)量崇众。求一共有多少種可能的價(jià)格滤蝠。就是個(gè)背包問題。

代碼

#include <stdio.h>
#include <iostream>
#include <bitset>
using namespace std;

int main(int argc, const char * argv[]) {
    int n, m;

    // 每種硬幣的價(jià)值
    int value[105];

    // 每種硬幣的數(shù)量
    int number[105];

    // 價(jià)格的可能性嘱巾，比如價(jià)格 i憨琳，如果 bitset 第 i 位為 true，則代表此價(jià)格可行旬昭，反之則不可行篙螟。
    bitset<100005> resultBitSet;
    
    while (true) {

        // 處理數(shù)據(jù)的輸入
        scanf("%d %d", &n, &m);
        if (n == 0 && m == 0) {
            return 0;
        }
        for (int i = 0; i < n; i++) {
            scanf("%d", &value[i]);
        }
        for (int i = 0; i < n; i++) {
            scanf("%d", &number[i]);
        }
        
        // 重置 resultBitSet
        resultBitSet.reset();

        // 從存錢罐中挨個(gè)取硬幣處理
        for (int i = 0; i < n; i++) {
            for (int t = 1; t <= number[i] && t*value[i] <= m; t++) {
                // 最關(guān)鍵的兩行代碼，<< 計(jì)算的是新增的可能價(jià)值问拘，|= 是在原有可能價(jià)值的基礎(chǔ)上累加新增的可能價(jià)值
                resultBitSet |= (resultBitSet << value[i]);

                // 這行其實(shí)也挺關(guān)鍵的遍略，做初始化，如果這行代碼順序出錯(cuò)也是得不出正確結(jié)果的
                resultBitSet.set(t*value[i]);
            }
        }
        
        // 以上的 for 循環(huán)在移位時(shí)會(huì)計(jì)算進(jìn)部分超過 m 價(jià)值的數(shù)據(jù)场梆，這里通過移位把這些數(shù)據(jù)移掉
        resultBitSet <<= (100005 - (m + 1));

        printf("%lu\n", resultBitSet.count());
    }
}

其實(shí)一直想找這樣一個(gè)可以直接移位的內(nèi)存塊墅冷，這樣處理起來就很方便了。不過說來慚愧或油，雖然 13 年左右寫過一年的 C++寞忿，但是不知道是當(dāng)時(shí)就不知道 bitset 還是后來這幾年不寫給忘了，反正就是沒想起來顶岸，所以我一開始寫的代碼是如下的（Time Limit Exceeded）：

#include <stdio.h>
#include<iostream>
#include <cstring>

int value[105];
int number[105];

bool result[100005];

// 處理輸入
bool processInput(int &n, int &m) {
    scanf("%d %d", &n, &m);
    if (n == 0 && m == 0) {
        return false;
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &value[i]);
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &number[i]);
    }
    return true;
}

// 計(jì)算結(jié)果
void calculate(int n, int m) {
    memset(result, 0, sizeof(result));
    
    for (int i = 0; i < n; i++) {
        if (number[i] <= m) {
            for (int k = m; k >= 1; k--) {
                if (result[k] && k + value[i] <= m) {
                    for (int t = 1; t <= number[i] && k + t * value[i] <= m; t++) {
                        result[k + t * value[i]] = true;
                    }
                }
            }
            for (int t = 1; t <= number[i] && t*value[i] <= m; t++) {
                result[t*value[i]] = true;
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    int n, m;
    while (processInput(n, m)) {
        calculate(n, m);
        int total = 0;
        for (int i = 1; i <= m; i++) {
            if (result[i]) {
                total++;
            }
        }
        printf("%d\n", total);
    }
    return 0;
}