HDOJ(HDU).1114 Piggy-Bank (DP 完全背包)

题意分析

裸的完全背包

代码总览

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define nmax 100000

#define INF 0x3f3f3f3f

using namespace std;

int we[nmax],va[nmax],dp[nmax];

struct item{

    int w;

    int v;

}arr[nmax];

int main()

{

    //freopen("in.txt","r",stdin);

    int t;

    scanf("%d",&t);

    while(t--){

        int e,f;

        scanf("%d%d",&e,&f);

        int n;

        scanf("%d",&n);

        memset(arr,0,sizeof(arr));

        memset(dp,INF,sizeof(dp));

        for(int i =1; i<=n; ++i){

            scanf("%d%d",&arr[i].v,&arr[i].w);

        }

        dp[0] = 0;

        for(int i =1 ;i<=n; ++i){

            for(int j = arr[i].w; j<=(f-e);++j)

                dp[j] = min(dp[j],dp[j-arr[i].w]+arr[i].v);

        }

        if(dp[f-e] == INF) printf("This is impossible.\n");

        else printf("The minimum amount of money in the piggy-bank is %d.\n",dp[f-e]);

    }

    return 0;

}