题解 | #称砝码#

思路：

1. 计算砝码的总重量max，剩余表示的重量不会大于max
2. 申请max+1的空间，判断剩余的重量是否有表示不到的，需要--

#include <stdio.h>

int main()
{
    int n = 0;
    int max = 0;    //表示最大重量
    scanf("%d", &n);  //砝码的种数
    int weight[n];    //重量
    int num[n];       //数量
    memset(weight, 0, n*sizeof(int));
    memset(num, 0, n*sizeof(int));
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &weight[i]);
        //printf("weight[%d] = [%d]\n", i, weight[i]);
    }
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &num[i]);
        //printf("num[%d] = [%d]\n", i, num[i]);
    }
    for(int i = 0; i < n; i++)    //得到最大重量
    {
        max += (weight[i] * num[i]);
    }
    //printf("max = [%d]\n", max);
    int map[max+1];
    memset(map, 0, (max+1)*sizeof(int));
    map[0] = 1;    //0也是重量
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < num[i]; j++)
        {
            for(int k = max-1; k >= 0; k--)
            {
                if(map[k])
                {
                    map[k+weight[i]] = 1;
                    //printf("[%d : %d : %d : %d]\n", i, j, k,k+weight[i]);
                }
            }
        }
    }
    int count = 0;
    for(int i = 0; i < max+1; i++)
    {
        if(map[i])
        {
            count++;
        }
    }
    printf("%d\n", count);
    return 0;
}