poj1837解题报告

godfrey90

这是一个很典型的动态规划中的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[k]*G[i];                if((value>=0)&&(value<=15000)){                    metrix[i][j]+=metrix[i-1][value];                }            }        }    }
最终得到G个砝码都放完时，值为0的那个状态的放法总数
Source CodeProblem: 1837User: godfrey90Memory: 1560KTime: 63MSLanguage: GCCResult: AcceptedSource Code#include <stdio.h>#define OFFSET 7500int metrix[20][15001];int C[20];int G[20];int cNum,gNum;int read(){    scanf("%d",&cNum);    scanf("%d",&gNum);    int i=0;    for(i=0;i<cNum;i++){        scanf("%d",&C[i]);    }    for(i=0;i<gNum;i++){        scanf("%d",&G[i]);    }}int main(){    memset(metrix,0,sizeof(metrix));    read();    int i=0,j=0;    int value = 0;    for(j=0;j<cNum;j++){        value = G[0]*C[j];        metrix[0][OFFSET+value]++;    }    int k=0;    for(i=1;i<gNum;i++){        for(j=0;j<=15000;j++){            for(k=0;k<cNum;k++){                value = j-C[k]*G[i];                if((value>=0)&&(value<=15000)){                    metrix[i][j]+=metrix[i-1][value];                }            }        }    }    printf("%d\n",metrix[gNum-1][OFFSET]);    return 0;}