题解 | #称砝码#

回溯

#include <iostream>
#include <unordered_map>
using namespace std;

const int MAX_LEN    = 11;
const int UN_VISITED = 0;
const int VISITED    = 1;

int ans = 0;
int max_sum = 0;

void backtrack(int index, int *w, int *cnt, int len, unordered_map<int, char> &map, int sum) {
    if (map[sum] == UN_VISITED) {
        ++ans;
        map[sum] = VISITED;
    }
    if (index == len) return ;
    for (int j = 0; j <= cnt[index]; ++j) {
        if (sum + w[index] * j > max_sum) break;
        backtrack(index + 1, w, cnt, len, map, sum + w[index] * j);
    }
}

int main(void) {
    int N;
    int *w= (int *)malloc(sizeof(int) * MAX_LEN);
    int *cnt = (int *)malloc(sizeof(int) * MAX_LEN);
    while (cin >> N) {
        unordered_map<int, char> map;
        for (int i = 0; i < N; ++i)
            cin >> w[i];
        for (int i = 0; i < N; ++i)
            cin >> cnt[i];
        max_sum = ans = 0;
        for (int i = 0; i < N; ++i)
            max_sum += (w[i] * cnt[i]);
        backtrack(0, w, cnt, N, map, 0);
        cout << ans << endl;
    }
    return 0;
}