杭电 1114 Piggy-Bank 动态规划

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

题意：题目意思是给一些硬币，有重量和价值，然后给一个罐子，问在能否在装满罐子的条件下，求到这个罐子的最小价值。

完全背包

#include<bits/stdc++.h>
#define _for(i,a,b) for(int i=a;i<b;i++)
#define rre(i,r,l) for(int i=(r);i>=(l);i--)
#define req(i,l,r) for(int i=(l);i<=(r);i++)
#define mem(a,b) memset(a,b,sizeof(a))
#define op operator
#define endl "\n"
#define MIN_SUM 0x80000000
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template<typename Q>
void inin(Q &x) {  //读入优化 
    x=0;
    int f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') {
        if(ch=='-')f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    x=f?-x:x;
}
#define inf 400000
struct node {
    int value;
    int space;
};
int main() {
    int n;
    node a[510];
    int t;
    int dp[10010];
    while(scanf("%d",&t)!=EOF) {
        while(t--) {
            mem(dp,0);
            int e,f;
            inin(e);
            inin(f);
            inin(n);
            int flag=0;
            _for(i,0,n) {
                inin(a[i].value);
                inin(a[i].space);
                if(a[i].space<=f-e) {  //提前判断 
                    flag=1;
                }
            }
            if(!flag) {
                printf("This is impossible.\n");
            } else {
                req(i,1,f-e)  //初始化，因为要求最小，所以设大点 
                    dp[i]=inf;
                _for(i,0,n) {
                    req(j,a[i].space,f-e) {   //背包九讲中的公式 
                        dp[j]=min(dp[j],dp[j-a[i].space]+a[i].value);
                    }
                }
                if(dp[f-e]!=inf) {//看是否装满了 
                    printf("The minimum amount of money in the piggy-bank is %d.\n",dp[f-e]);
                } else {
                    printf("This is impossible.\n");
                }
            }

        }
    }

    return 0;
}