题解 | #称砝码#

用动态规划做。思路是把所有的砝码展开，用数组w来保存砝码，例如原本有3个重量为9的法码，那就直接压入3个9到数组w中。 最后得到一个砝码数组。砝码数组中的砝码之和为max_weight，表示所有砝码加起来可以称量的最大重量。

动态规划数组dp[i]是一个布尔型数组，如果为真表示重量i可以被称量。

第一层循环所有砝码，第二层循环 1...max_weight，由于砝码w[i]的加入，假设是一个重量为5的砝码，当前要考虑的重量是8能不能被称量，如果dp[3]为true，即3能被称量，那么加上这个重量为5的砝码，则8一定能被称量。按这个思路，伪代码如下：

for i = 1 .. w.size:
  for j = 1 ... max_weight:
     if w[j - w[i]] == True:
         w[j] = True;

下面的C++代码实现中，使用到了滚动数组。另外，测试用例的最后一个用例是有问题的，因为题设中每组砝码的数量范围是[1, 6]，但是测试用例的最后一组砝码数量是10。

#include <iostream>
#include <set>
#include <vector>

using namespace std;
bool dp[2010 * 100]; // 最后一组测试用例砝码数量用了10，这里需要乘以100，否则长度不够。

int main()
{
    int n;
    while(cin >> n)
    {
        vector<int>w;
        int max_weight = 0, tmp;
        w.push_back(0); // 无意义占位符
                
        for(int i = 1; i <= n; i++) { cin >> tmp; w.push_back(tmp); } 
        for(int i = 1; i <= n; i++)
        {
            cin >> tmp;
            for(int j = 0; j < tmp - 1; j++)
                w.push_back(w[i]);
            max_weight += tmp * w[i];
        }
        // 初始化动态规范数组
        for(int i = 0; i <= max_weight; i++)
            dp[i] = false;
        dp[0] = true; // 关键，初始启动
        // 动态规划查找
        for(int i = 1; i < w.size(); i++)
            for(int j = max_weight; j >= w[i]; j--)
                if(dp[j-w[i]]) dp[j] = true;
        // 统计结果
        int res = 0;
        for(int i = 0; i <= max_weight; i++)
            if(dp[i]) res++;
        cout << res << endl;
    }
    return 0;
}