称砝码问题

最后更新于: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 &gt;&gt; n;
    int max_wight = 0;
    vector&lt;int&gt; nums(n), wights(n);

    for (int i = 0; i &lt; n; i++)
        cin &gt;&gt; wights[i];
    for (int i = 0; i &lt; n; i++) {
        cin &gt;&gt; nums[i];
        max_wight += wights[i] * nums[i]; //求最大可称重的值
    }

    //set内是可以称重的值,元素互斥单调增
    set&lt;int&gt; s;
    s.insert(max_wight);

    //进行n次循环;
    //对于第i次循环,将set中元素从小到大依次取出,
    //减去k * wights[i],表示少使用k个质量为wights[i]的砝码
    //也可以作为可称重的值;只要这个值是大于0的即可。
    for (int i = 0; i &lt; n; i++) {
        set&lt;int&gt;::iterator iter = s.begin();
        while (iter != s.end()) {
            for (int k = 1; k &lt;= nums[i] &amp;&amp; *iter - k * wights[i] &gt; 0; k++)
                s.insert(*iter - k * wights[i]);
            iter++;
        }
    }
    s.insert(0);
    cout &lt;&lt; s.size() &lt;&lt; endl;
    return 0;
}
                </div>
    
';