题目大意：
有一个天平上有C个挂钩，分别在不同的位置上，用C个整数表示。正整数代表在原点右侧，负整数代表在左侧，就相当于一个数轴。有G个砝码，求有多少种平衡情况。
思路：
这是一个01背包问题。
每勾上一个砝码就是一个新阶段。
每一个新阶段都是在原来的出现过的状态上更新的。
状态方程dp [ i ][ j+ w[ i ]*c[ k ] ]= ∑（dp[ i-1 ][ j ] ）；
下面是代码：
#include <stdio.h> #include <string.h> int dp[21][15005]; int main() { int c,g,i,j,k; while(scanf("%d%d",&c,&g)!=EOF) { int c1[25],w[25]; for(i=0;i<c;i++) { scanf("%d",&c1[i]); } for(i=0;i<g;i++) { scanf("%d",&w[i]); } memset(dp,0,sizeof(dp)); dp[0][7503]=1; for(i=1;i<=g;i++) { for(j=0;j<15005;j++) { if(dp[i-1][j]) { for(k=0;k<c;k++) { dp[i][j+w[i-1]*c1[k]]+=dp[i-1][j]; } } } } printf("%d\n",dp[g][7503]); } return 0; }
转载于:https://www.cnblogs.com/lin375691011/p/3996746.html
相关资源：JAVA上百实例源码以及开源项目