题解 | #称砝码# 动态规划 背包

#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
int weight[15],num[15],ans,n;
bool f[15][200001];
//设f[i][j]表示从 前i种 砝码中选出 总重量为j 的砝码的方案是否可行，f[i][j]=1表示可行，f[i][j]=0表示不可行
int main() {
    cin>>n;
    int total=0;
    for(int a=1;a<=n;a++) cin>>weight[a];
    for(int a=1;a<=n;a++) cin>>num[a],total+=num[a];
    f[0][0]=1;
	//初值: f[0][0]=1, 从 0种 砝码中选出 总重量为0 的砝码的方案可行
  
    for(int a=1;a<=n;a++)
    {
        for(int b=0;b<=200000;b++) f[a][b]=f[a-1][b];
	  //不选第a种砝码
	  
        for(int b=0;b<=num[a];b++) //枚举选砝码的个数
        {
            for(int c=b*weight[a];c<=200000;c++)
            {
                f[a][c]=f[a-1][c-b*weight[a]] | f[a][c];
			  //选第a种砝码，因为求解的是可行性，所以这里把 不选第a种 与 选第a种 的结果相或
            }
        }
    }
    for(int a=0;a<=200000;a++) if(f[n][a]==1) ans++;
  //遍历查询从 前n种 砝码中选出 总重量为a 的砝码的方案是否可行，统计答案个数
    cout<<ans;
  //输出答案
    return 0;
}
// 64 位输出请用 printf("%lld")