称砝码问题

最后更新于:2022-04-01 16:17:38

# 题目描述 有一组砝码,重量互不相等,分别为m1、m2、m3……mn;它们可取的最大数量分别为x1、x2、x3……xn。  现要用这些砝码去称物体的重量,问能称出多少种不同的重量。  Input 测试数据第一行一个整数n(n<=10),表示有多种不同的砝码;  第二行n个整数(中间用空格分隔),m1、m2、m3……mn,分别表示n个砝码的重量;(1<=mi<=20)  第三行n个整数(中间用空格分隔),x1、x2、x3……xn,分别表示n个砝码可取的最大数量。(1<=xi<=20)  Output 每组数据输出仅一行,一个整数,表示利用给定的砝码可以称出的不同的重量数。  注:包括0。  Sample Input 2 1 2 2 1 Sample Output 5 ~~~ //称砝码 int main() { int n; cin >> n; int max_wight = 0; vector<int> nums(n), wights(n); for (int i = 0; i < n; i++) cin >> wights[i]; for (int i = 0; i < n; i++) { cin >> nums[i]; max_wight += wights[i] * nums[i]; //求最大可称重的值 } //set内是可以称重的值,元素互斥单调增 set<int> s; s.insert(max_wight); //进行n次循环; //对于第i次循环,将set中元素从小到大依次取出, //减去k * wights[i],表示少使用k个质量为wights[i]的砝码 //也可以作为可称重的值;只要这个值是大于0的即可。 for (int i = 0; i < n; i++) { set<int>::iterator iter = s.begin(); while (iter != s.end()) { for (int k = 1; k <= nums[i] && *iter - k * wights[i] > 0; k++) s.insert(*iter - k * wights[i]); iter++; } } s.insert(0); cout << s.size() << endl; return 0; } ~~~
';