首页 > 代码库 > HDU1114 Piggy-Bank

HDU1114 Piggy-Bank

2024-07-15 03:10:50   220人阅读

因为完全背包刚开始学,以前学过忘记了..嘻嘻,所以下午跑到图书馆去想题目去了.

这题背包比较重要的一个点就是要装满背包---这个是关于初始化的问题;

开一个数组DP保存值,除了DP[0]=0;其他设为无穷大(正负看题意要求,这题要求正无穷大,其实也没无穷大..相对大,就是要比所有数据加起来打);

注意不要溢出,我上来就定义了0X7FFFFFFF..查了几分钟才发现是溢出了..不过还好;

下面给出代码..

#include<iostream>#define maxn 10001#define number 501*50000using namespace std;int w[maxn],v[maxn],dp[maxn],t,n,a,b;int min(int a,int b){    return a<b?a:b ;}int main(){    //freopen("1114.txt","r",stdin);    while(~scanf("%d",&t))    {        while(t--)        {         scanf("%d %d",&a,&b);        int i,j;        int m=b-a;            memset(v,0,sizeof(v));        memset(w,0,sizeof(w));       for(i=1;i<=m;i++)           dp[i]=number;        dp[0]=0;        scanf("%d",&n);        for(i=1;i<=n;i++)            scanf("%d %d",w+i,v+i);             for(i=1;i<=n;i++)             for(j=v[i];j<=m;j++)                dp[j]=min(dp[j],dp[j-v[i]]+w[i]);            if(dp[m]==number)                printf("This is impossible.\n");            else                printf("The minimum amount of money in the piggy-bank is %d.\n",dp[m]);    }    }    return 0;}

 


联系
我们