HJ41.称砝码

解法一（回溯法，超过时间限制）：

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

unordered_set<int> rst;

int sum(const vector<int>& vec) {
    int ret = 0;
    for (auto& i : vec) ret += i;
    return ret;
}

void backtrack(const vector<int>& weights, vector<int>& path, int cur) {
    rst.insert(sum(path));
    if (path.size() == weights.size()) {
        return;
    }
    unordered_set<int> vis;
    for (int i = cur; i < weights.size(); ++i) {
        if (vis.count(weights[i]) == 0) {
            vis.insert(weights[i]);
            path.emplace_back(weights[i]);
            backtrack(weights, path, i + 1);
            path.pop_back();
        }
    }
}

int weightMethod(vector<int> weights) {
    vector<int> path {};
    backtrack(weights, path, 0);
    return (int)rst.size();
}

vector<int> spread(const vector<int>& weight, const vector<int>& num, int n) {
    vector<int> weights;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < num[i]; ++j) {
            weights.emplace_back(weight[i]);
        }
    }
    return weights;
}

int main() {
    int n = 0, temp = 0;
    vector<int> weight, num;
    while (cin >> n) {
        for (int i = 0; i < n; ++i) {
            cin >> temp;
            weight.emplace_back(temp);
        }
        for (int i = 0; i < n; ++i) {
            cin >> temp;
            num.emplace_back(temp);
        }
        cout << weightMethod(spread(weight, num, n)) << endl;
        weight.clear();
        num.clear();
        rst.clear();
    }
    return 0;
}

解法二：

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

/*
      0                ->    0
+1    0 1              ->    0 1
+1    0 1 1 2          ->    0 1 2
+2    0 1 2 2 3 4      ->    0 1 2 3 4
*/
int weightMethod(const vector<int>& weights) {
    unordered_set<int> rst { 0 };
    for (auto& i : weights) {
        unordered_set<int> temp(rst);
        for (auto& j : temp) {
            rst.insert(i + j);
        }
    }
    return (int)rst.size();
}

// 展开输入，摊成一个数组
vector<int> spread(const vector<int>& weight, const vector<int>& num) {
    vector<int> weights;
    for (int i = 0; i < (int)weight.size(); ++i) {
        for (int j = 0; j < num[i]; ++j) {
            weights.emplace_back(weight[i]);
        }
    }
    return weights;
}

int main() {
    int n = 0;
    while (cin >> n) {
        vector<int> weight(n), num(n);
        for (auto& i : weight) cin >> i;
        for (auto& i : num) cin >> i;
        cout << weightMethod(spread(weight, num)) << endl;
    }
    return 0;
}

解题思路：

难点1：熟悉回溯的话可以想到解法一，但很容易超过时空限制，题目只是要求最终的结果，并不需要每种方式的排列方式，所以没必要使用回溯；

难点2：不容易在考试的时候就能看出以下规律，看出的话基本能想到使用set来求解了；

/*
      0                ->    0
+1    0 1              ->    0 1
+1    0 1 1 2          ->    0 1 2
+2    0 1 2 2 3 4      ->    0 1 2 3 4
*/

知识点：

知识点1：vector可以确定大小之后直接写入，，，学习到了；

    int n = 0;
    while (cin >> n) {
        vector<int> weight(n), num(n);
        for (auto& i : weight) cin >> i;
        for (auto& i : num) cin >> i;
        cout << weightMethod(spread(weight, num)) << endl;
    }

知识点2：set里面有set_intersection（取集合交集）、set_union（取集合并集）、set_difference（取集合差集）、set_symmetric_difference（取集合对称差集）等函数，包含在algorithm头文件当中；

#include <set>                           // std::set
#include <algorithm>                     // std::set_union

std::set<int> set1 { 1, 2, 3, 4, 5, 6 }; // Contains 6 5 4 3 2 1
std::set<int> set2 { 4, 5, 6, 7, 8, 9 }; // Contains 9 8 7 6 5 4
std::set<int> result;                    // Elements in descending sequence

std::set_union(std::begin(set1), std::end(set1),
               std::begin(set2), std::end(set2),
               std::inserter(result, std::begin(result)));