HDOJ1114解题报告【完全背包】

题目地址：

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

题目概述：

　　这个题的难度估计就是在读题上了……

　　给出n组{p，w}，其中p为价值，w为重量，再给出一个容器的容积，请填满容器并使总价值最小，每组都可以重复使用。

大致思路：

　　看了题目概述之后是不是瞬间懂了，很显然的完全背包嘛。

　　dp[i]表示容积为i时最小的价值，转移方程是：dp[i]=min(dp[i],dp[i-w]+p)

　　初始化为inf，dp[0]=0。

代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <ctime>
#include <map>
#include <stack>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;

#define sacnf scanf
#define scnaf scanf
#define scanfi(x) scanf("%d",&x)
#define scanfd(x) scanf("%lf",&x)
#define scanfl(x) scanf("%lld",&x)
#define scanfc(x) scanf("%c",&x)
#define scanfs(x) scanf("%s",x)
#define maxn  510
#define maxm 10010
#define inf 1061109567
#define Eps 0.00001
const double PI=acos(-1.0);
#define mod 1000000007
#define MAXNUM 10000
void Swap(int &a,int &b) {int t=a;a=b;b=t;}
int Abs(int x) {return (x<0)?-x:x;}
typedef long long ll;
typedef unsigned int uint;

int dp[maxm];

int main()
{
    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);
    //clock_t st=clock();
    int T;scanf("%d",&T);
    while(T--)
    {
        int E,F,p,w,n;scanf("%d%d",&E,&F);F-=E;
        memset(dp,0x3f,sizeof(dp));scanf("%d",&n);
        dp[0]=0;
        for(int i=1;i<=n;i++)
        {
            scnaf("%d%d",&p,&w);
            for(int j=w;j<=F;j++)
                dp[j]=min(dp[j],dp[j-w]+p);
        }
        if(dp[F]==inf) printf("This is impossible.
");
        else printf("The minimum amount of money in the piggy-bank is %d.
",dp[F]);
    }
    //clock_t ed=clock();
    //printf("

Time Used : %.5lf Ms.
",(double)(ed-st)/CLOCKS_PER_SEC);
    return 0;
}