HDU 1114 完全背包+判断能否装满-白红宇

HDU 1114 完全背包+判断能否装满

阅读量：6981 次

发布时间：2019-06-27

本文共 980 字，大约阅读时间需要 3 分钟。

题意给出一个存钱罐里的钱币重量给出可能的n种钱币重量以及价值求存钱罐中钱币的最小价值若不可能另有输出

在裸的完全背包上加了一点东西即判断这个背包能否被装满

初始化 dp[0]=0 其余的都使用for循环设置成INF 以达到求min的目的

最后如果dp[v]还是那么大就说明它根本没有通过前面的方式被改变即不能被装满

#include
     
      #include
      
       #include
       
        #include
        #include
         
          using namespace std;int e,f;int val[505];int vol[505];int dp[10050];int main(){int t;scanf("%d",&t);while(t--){    scanf("%d%d",&e,&f);    int v=(f-e);    int n;    scanf("%d",&n);    for(int i=1;i<=n;i++)    {        scanf("%d%d",&val[i],&vol[i]);    }    dp[0]=0;    for(int i=1;i<=v;i++)    {        dp[i]=500000000;    }    for(int i=1;i<=n;i++)    {        for(int k=vol[i];k<=v;k++)        {            dp[k]=min(dp[k],dp[k-vol[i]]+val[i]);        }    }    if(dp[v]==500000000)    {        printf("This is impossible.\n");    }    else printf("The minimum amount of money in the piggy-bank is %d.\n",dp[v]);}}