一开始想用集合枚举的方式，后来看了别人的解题报告发现原来通过转换可以变为一个01背包问题。
dp[i][j] 表示前 i 个砝码，平衡系数为 j 的时候种类个数。其中 j 为7500为平衡状态（7500 = 15*20*20*25/2，因为不允许存在负数为数组下标，所以除以2）。
这里当在左边的时候 j 减去一个数，在右边的时候加上一个数。当左右平衡的时候即会回到7500这个平衡状态。
方程如下：dp[i][j+w[i]*p[k]] += dp[i-1][j]
代码：
#include#include #include using namespace std; #define LLEN 100 int p[LLEN], w[LLEN]; int dp[21][15005]; int main() { int c, g; while(scanf("%d%d", &c, &g) != EOF) { memset(dp, 0, sizeof(dp)); dp[0][7500] = 1; for(int i = 1; i <= c; i++) { scanf("%d", &p[i]); } for(int i = 1; i <= g; i++) { scanf("%d", &w[i]); } for(int i = 1; i <= g; i++) { for(int j = 0; j < 15001; j++) { if(dp[i-1][j]) { for(int k = 1; k <= c; k++) { dp[i][j+w[i]*p[k]] += dp[i-1][j]; } } } } printf("%d\n", dp[g][7500]); } return 0; }