hdu 1114 Piggy-Bank（我的第一个完全背包）

Piggy-Bank

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2940????Accepted Submission(s): 1452

?

for i=1..N

??? for v=0..V

??????? f[v]=max{f[v],f[v-cost]+weight}

链接：http://acm.hdu.edu.cn/showproblem.php?pid=1114

代码：

?

#include <iostream>#include <stdio.h>#include <memory.h>using namespace std;const int INF = 99999999;int c[50005], w[10005];int bag[10005];int N, V, Z;void _com_bag()     //完全背包：顺序！{    int i, j;    for(i = 0; i <= Z; i++) bag[i] = INF;    bag[0] = 0;    for(i = 0; i < N; i++)    {        for(j = c[i]; j <= Z; j++)        {            bag[j] = min(bag[j], bag[j-c[i]] + w[i]);        }    }}int main(){    int i, t, E, F;    scanf("%d", &t);    while(t--)    {        scanf("%d %d", &E, &F);        Z = F - E;        scanf("%d", &N);        for(i = 0; i < N; i++)            scanf("%d %d", &w[i], &c[i]);        _com_bag();        if(bag[Z] != INF)            printf("The minimum amount of money in the piggy-bank is %d.\n", bag[Z]);        else            printf("This is impossible.\n");    }    return 0;}

?