现有n种砝码,重量互不相等,分别为 m1,m2,m3…mn ;
每种砝码对应的数量为 x1,x2,x3…xn 。现在要用这些砝码去称物体的重量(放在同一侧),问能称出多少种不同的重量。
注:
称重重量包括 0
#include#include #include #include using namespace std; const int N = 15, M = 2010; int n, m; int w[N], v[N]; int main() { cin >> n; for(int i=1; i<=n; i++) cin >> v[i]; for(int i=1; i<=n; i++) cin >> w[i]; unordered_set S = {0}; for(int i=1; i<=n; i++) { unordered_set tmp; for(auto &c : S) { for(int j=0; j<=w[i]; j++) { tmp.insert(c + j * v[i]); } } S = tmp; } cout << S.size() << endl; return 0; }
输入:
4
1 2 3 4
2 1 4 5
输出:41



