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[k]*G[i];
                if((value>=0)&&(value<=15000)){
                    metrix[i][j]+=metrix[i-1][value];
                }
            }
        }
    }

最终得到G个砝码都放完时，值为0的那个状态的放法总数

Source Code

Problem: 1837		User: godfrey90
Memory: 1560K		Time: 63MS
Language: GCC		Result: Accepted
Source Code
#include <stdio.h>
#define OFFSET 7500

int 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;
}