首页 > 代码库 > hdu1114 完全背包

hdu1114 完全背包

题意:给出钱罐的重量,然后是每种钱的价值和重量,问钱罐里最少可能有多少钱。

完全背包。

代码:

#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>using namespace std;int p[505],w[505];int dp[10005];int main(){    int T;    cin>>T;    while(T--)    {        int m1,m2,m,n;        cin>>m1>>m2;        m=m2-m1;        cin>>n;        for(int i=1; i<=n; i++)            cin>>p[i]>>w[i];        memset(dp,0x3f,sizeof(dp));        dp[0]=0;        for(int i=1; i<=n; i++)            for(int j=w[i]; j<=m; j++)                dp[j]=min(dp[j],dp[j-w[i]]+p[i]); //价值取最小        if(dp[m]==0x3f3f3f3f) cout<<"This is impossible."<<endl;        else cout<<"The minimum amount of money in the piggy-bank is "<<dp[m]<<.<<endl;    }    return 0;}

 

hdu1114 完全背包