poj1837解题报告
这是一个很典型的动态规划中的01背包问题，G个砝码，每个砝码有C种放法。我们就可以按砝码的个数划分状态，共有G种状态，每种状态有多个选择，每次加一个砝码为一次状态转移，状态转移方程为:for(i=1;i<gNum;i++){ for(j=0;j<=15000;j++){ for(k=0;k<cNum;k++){ value = j-C*G; if((value>=0)&&(value<=15000)){ metrix+=metrix; } } } }
最终得到G个砝码都放完时，值为0的那个状态的放法总数
Source CodeProblem: 1837User: godfrey90Memory: 1560KTime: 63MSLanguage: GCCResult: AcceptedSource Code#include <stdio.h>#define OFFSET 7500int metrix;int C;int G;int cNum,gNum;int read(){ scanf("%d",&cNum); scanf("%d",&gNum); int i=0; for(i=0;i<cNum;i++){ scanf("%d",&C); } for(i=0;i<gNum;i++){ scanf("%d",&G); }}int main(){ memset(metrix,0,sizeof(metrix)); read(); int i=0,j=0; int value = 0; for(j=0;j<cNum;j++){ value = G*C; metrix++; } int k=0; for(i=1;i<gNum;i++){ for(j=0;j<=15000;j++){ for(k=0;k<cNum;k++){ value = j-C*G; if((value>=0)&&(value<=15000)){ metrix+=metrix; } } } } printf("%d\n",metrix); return 0;}
页:
[1]